CSC148 - Lab 7
Ternary Heap
In our implementation of a priority queue, we implemented a heap as an (almost...) complete binary tree. There are of course alternatives. We can implement as an almost complete ternary tree, where each node has a left child, a middle child, and a right child. The heap property maintains unchanged; the value stored on each node must not be greater than that stored on any of its children.
Download heap.py and modify it so that instead of using a binary tree, it uses a ternary tree. Your first step should be to figure out given a node at index i, where its parent and three children are located. The insert and extract_min algorithms should be very similar.
How does the height of a ternary tree compare to that of a binary tree (if both have n nodes)? Does this difference matter?
Write some nose tests to make sure that your heap is working correctly.
k-ary Heap
Now, attempt to implement a heap as an almost complete k-ary tree, where each node has at most k children. Derive formulas for the index of the parent of a given node, as well as its (up to) k children. Use the same starter code, heap.py, and modify the constructor to take k as a parameter. Write some tests to make sure your heap is working correctly.