A heap is a data structure that is a type of tree. According to Wikipedia, a data structure is said to be a heap if it satisfies the following "heap property":
If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. (See the diagram below.)
Heaps make it easy to access the highest or lowest value element in a set of data (always keeping it at the "top" of the heap). A max heap always keeps the maximum element at the root node (the topmost node), and a min heap always keeps the minimum element at the root.
An example of a min heap, heap
, which shows how the heap changes when the push
method is called:
For this lab, you will implement a MinHeap class that stores data and always keeps track of its minimum element as its root. It will have a push method as illustrated by the above diagram, as well as a pop method that ensures the minimum element will always be stored in the root.
Run rspec --fail-fast and make the tests pass one at a time.