Heap Sort

Posted on | In ,

Heap sort is an in-place sorting algorithm that uses a heap data structure. It first transforms the list into a max-heap, then repeatedly pops the maximum value and places it at the end of the list. To build the heap in-place, the list is treated as a complete binary tree. With this assumption, it traverses from the bottom up and applies downHeap to convert the binary tree into a valid heap. This step takes $O(n \log n)$ (in fact, it is known to run in $O(n)$ with a careful analysis). After that, repeatedly swapping the root with the last element and restoring the heap property yields the sorted result. Overall, heap sort is an $O(n \log n)$ in-place sorting algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def downHeap(lst, length, idx):
    if 2 * idx + 2 < length:
        if lst[idx] < lst[2 * idx + 1]:
            if lst[2 * idx + 1] < lst[2 * idx + 2]:
                lst[idx], lst[2 * idx + 2] = lst[2 * idx + 2], lst[idx]
                downHeap(lst, length, 2 * idx + 2)
            else:
                lst[idx], lst[2 * idx + 1] = lst[2 * idx + 1], lst[idx]
                downHeap(lst, length, 2 * idx + 1)
        elif lst[idx] < lst[2 * idx + 2]:
            lst[idx], lst[2 * idx + 2] = lst[2 * idx + 2], lst[idx]
            downHeap(lst,length, 2 * idx + 2)
    elif 2 * idx + 1 < length:
        if lst[idx] < lst[2 * idx + 1]:
            lst[idx], lst[2 * idx + 1] = lst[2 * idx + 1], lst[idx]
            downHeap(lst, length, 2 * idx + 1)
    else:
        pass

def listToHeap(lst):
    height = 0
    sumE   = 0
    while sumE < len(lst):
        height += 1 
        sumE   *= 2
        sumE   += 1
    for i in range(height - 2, -1, -1):
        for j in range(2 ** i - 1, 2**(i + 1) - 1):
            downHeap(lst, len(lst), j)

def heapSort(lst):
    listToHeap(lst)
    for i in range(len(lst)-1, 0, -1):
        lst[0], lst[i] = lst[i], lst[0]
        downHeap(lst, i, 0)

#Test code
import random

if __name__ == "__main__":
    for i in range(1000):
        lst = []
        for j in range(1000):
            lst.append(random.randint(0,10000))
        targetIdx = random.randint(0,len(lst) - 1)
        lst2 = list(lst)

        #Will crush the qsort
        #lst2[0] = 0

        heapSort(lst2)
        if sorted(lst) != lst2:
            print('wrong result for heapSort')
            raise
    print('Every thing done well!')