迭代就地子列表堆排序python实现

Question

我发现python的heap sort有不同的版本，但似乎找不到符合我需要的版本。你知道吗

Iterative Heap Sort是我找到的最接近的， 但我不太明白如何改变它来处理子列表 （索引开始，索引结束）并保持原位。你知道吗

如果我答对了，我会把答案贴在这里。你知道吗

如果有人能用C或Java实现，那就太棒了。你知道吗

Answer 1

我想怎么做就怎么做。 此代码处理对象并按特定属性排序。你知道吗

def buildMaxHeap(arr, arrayLength, indexStart, attr):
    for i in range(arrayLength):

        # if child is bigger than parent
        if getattr(arr[indexStart + i], attr) > getattr(arr[indexStart + int((i - 1) / 2)], attr):
            j = i

            # swap child and parent until
            # parent is smaller
            while getattr(arr[indexStart + j], attr) > getattr(arr[indexStart + int((j - 1) / 2)], attr):
                (arr[indexStart + j],
                 arr[indexStart + int((j - 1) / 2)]) = (arr[indexStart + int((j - 1) / 2)], arr[indexStart + j])
                j = int((j - 1) / 2)


def heapSort(arr, arrayLength, indexStart, attr):
    buildMaxHeap(arr, arrayLength, indexStart, attr)

    for i in range(arrayLength - 1, 0, -1):

        # swap value of first indexed
        # with last indexed
        arr[indexStart + 0], arr[indexStart + i] = arr[indexStart + i], arr[indexStart + 0]

        # maintaining heap property
        # after each swapping
        j, index = 0, 0

        while True:
            index = 2 * j + 1

            # if left child is smaller than
            # right child point index variable
            # to right child
            if (index < (i - 1) and getattr(arr[indexStart + index], attr) < getattr(arr[indexStart + index + 1], attr)):
                index += 1

            # if parent is smaller than child
            # then swapping parent with child
            # having higher value
            if index < i and getattr(arr[indexStart + j], attr) < getattr(arr[indexStart + index], attr):
                arr[indexStart + j], arr[indexStart + index] = arr[indexStart + index], arr[indexStart + j]

            j = index
            if index >= i:
                break