Heap sort

Posted on | In

Heap sort is an in-place algorithm that sorts the list with heap. It first changes a list to the heap and then keeps poping it and push the maximum value to the end of the list. To change a list to the heap in-place, list is assumed to be form of complete binary tree. With this assumption, it read from bottom to up and downHeap to change complete binary tree to heap. This takes $O(n log n)$(Infact, it is known to be $O(n)$ with carefull analysis). After that, just pop head and push it to end of the list. As a result, it is $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!')