Итеративная реализация под-списка Heap Sort Python

Question

Я нашел разные версии сортировки кучи для python, но я не могу найти ту, которая соответствует моим потребностям.

Итеративная сортировка кучи - самая близкая из найденных мной, но я не могу понять, как изменить его, чтобы он работал с подсписком (начало индекса, конец индекса) и оставался на месте.

Если я правильно понял, я опубликую свой ответздесь.

Если у кого-то есть реализация даже на 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