Python Data Structures and Algorithms

Heap sort

In Chapter 8, Graphs and Other Algorithms, we implemented the (binary) heap data structure. Our implementation always made sure that after an element has been removed or added to a heap, the heap order property is maintained by using the sink and float helper methods.

The heap data structure can be used to implement the sorting algorithm called the heap sort. As a recap, let's create a simple heap with the following items:

    h = Heap()     unsorted_list = [4, 8, 7, 2, 9, 10, 5, 1, 3, 6]     for i in unsorted_list:         h.insert(i)     print("Unsorted list: {}".format(unsorted_list)) 

The heap, h, is created and the elements in the unsorted_list are inserted. After each method call to insert, the heap order property is restored by the subsequent ...