

In [1]:

    
import numpy as np

from IPython.display import clear_output
from pjdiagram import *
from ipywidgets import *

from heapsort import heap_sort_example, build_heap_example
from heap import percolate_down

Heap Sort

Summary

Performance	Complexity
Worst-case	$O(n\log{n})$
Best-case	$O(n\log{n})$
Average	$O(n\log{n})$
Worst-case space	$O(1)$

Notes

The time complexity for heap sort in all cases make it a good choice when there need to be guarantees for runtime. Additionally, heap sort requires a constant amount of memory, as it can sort in-place.

Algorithm

It is possible implement heap sort by using heap_insert and heap_pop (see notes on heaps). However, both of these operations require the allocation of additional space. Instead, we can perform the same operations in place.

The function build_heap applies the function percoluate_down on each non-leaf node in the tree starting at the bottom.



In [2]:

    
def build_heap(lst):
    # last non-leaf node
    nonleaf_nodes = len(lst)/2
    
    # start at bottom work up for each node
    for i in range(nonleaf_nodes-1, -1, -1):
        percolate_down(lst, i, len(lst))

a visualize demonstration of what build_heap is doing:



In [3]:

    
build_heap_example()

which allows us to define:



In [4]:

    
def heap_sort(lst):
    build_heap(lst)
 
    # build up list starting from largset at back to smallest up front
    for i in range(len(lst)-1, 0, -1):      
        # move largest value to the back
        lst[0], lst[i] = lst[i], lst[0]     
                 
        # re-heapify tree
        percolate_down(lst, 0, i)
 
    return lst

and we can see the sort in action:



In [5]:

    
heap_sort_example()