Nice work! You’ve implemented a min-heap in Python, and that’s no small feat (although it could efficiently track the smallest feat).
MinHeap tracks the minimum element as the element at index
1 within an internal Python list.
When adding elements, we use
.heapify_up() to compare the new element with its parent, making swaps if it violates the heap property: children must be greater than their parents.
When removing the minimum element, we swap it with the last element in the list. Then we use
.heapify_down() to compare the new root with its children, swapping with the smaller child if necessary.
Heaps are so useful because they’re efficient in maintaining their heap properties. Building a heap using elements that decreased in value would ensure that we continually violated the heap property. How many swaps would that cause?
Run the code in script.py to see how many swaps are made in a dataset of