python 堆排序

import copy

 

def heap_sort(hlist):

    def heap_adjust(parent):

        child = 2 * parent + 1  # left child

        while child < len(heap):

            if child + 1 < len(heap):

                if heap[child + 1] > heap[child]:

                    child += 1  # right child

            if heap[parent] >= heap[child]:

                break

            heap[parent], heap[child] = heap[child], heap[parent]

            parent, child = child, 2 * child + 1

 

    heap, hlist = copy.copy(hlist), []

    for i in range(len(heap) // 2, -1, -1):

        heap_adjust(i)

    while len(heap) != 0:

        heap[0], heap[-1] = heap[-1], heap[0]

        hlist.insert(0, heap.pop())

        heap_adjust(0)

    return hlist

 

hlist = heap_sort([4,5,6,7,3,2,6,9,8])

print(hlist)