In Chapter 8, Graphs and Other Algorithms, we implemented a binary heap data structure. Our implementation always made sure that, after an element had been removed or added to a heap, the heap order property was maintained, by using the sink() and arrange() helper methods.
The heap data structure can be used to implement a 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 call to the float method. After the loop is terminated, element 4 will be at the top of...
