Python : Binary Heap

The flip heap is a binary heap. It is not necceraly balanced. The key operation of the flip heap is the merge operation which takes two heaps and turns them into one. It work in two phases. First, it takes the left paths of the two heaps and merges them into one heap. Second, it takes all the nodes on this left path and flips the left and right children so that the values on the left path become a the right path.

Given two heaps to merge: First merge the left paths: 1 Then flip the left lath to be a a right path: Insert and extract-min are easy once you have merge. The insert operation creates a new one-node heap and merges it with the existing heap. The extract-min operation removes the root; this leaves two heaps which you merge into one heap. Coding You must create a new heap class, call it PQ which supports the merge, insert and extract-min operations (only). You can not store the heap in an array as the tree is not balanced. You could use the binary tree code from the book, but I recommend you simply start from scratch as this is probably easier. Also to keep it simple, have the heap just stores keys, not key-value pairs like many of the classes in the book.

Hints: First, you only need a node class with left and right child pointers, not parent pointers.