Description
For this lab you will implement another priority queue structure—the min-max heap. In addition to the discussion in class you can find more information in problem 6.18 on page 285 in the text. There is also a paper entitled “Min-Max Heaps and Generalized Priority Queues” (by Atkinson, et. al. from the Communications of the ACM, Volume 29, Number 10, p. 996) that you may use as another reference.
As a quick refresher, recall that a min-max heap is one in which the levels alternate with even numbered levels (root is at level 0) being min levels and odd numbered levels being max levels. Thus a key on a min level is less than or equal to the keys of all of its descendants and a key on a max level is larger than or equal to all of its descendants. This means when building the heap you will need to do comparisons with grandparents and grandchildren. You should be able to modify your binary heap functions from a previous lab to construct the corresponding functions for the minmax heap.
First task: Write a buildheap function that will take an array of integers and construct a minmax heap from it. Be sure you check that this is working correctly before you implement the other operations. Build a minmax heap with 25 – 50 integers and then print out the array containing those values. That verification (test data set and resulting tree) must be included in your lab submission. You should be able to easily draw the tree (by hand is fine) to make sure that the min-max heap is built correctly.
Second task: Implement functions to insert a new item into the heap, perform a deletemin operation, and perform a deletemax operation. Again, your submission must contain “proof” that these are working correctly. When you know your functions are working properly, construct a minmax heap with 50 distinct integers in the range between 1 and 100 and do the following sequence of insert, deletemin and deletemax operations. Print out the heap before starting the operations and again after each delete operation. (Just print out the array.)
insert 5, insert 87, deletemax, deletemin, insert 50, deletemax, reinsert the element just deleted, insert 2, insert 1, insert 100, insert 99, deletemin, deletemax, deletemin, deletemax, deletemax, deletemax.
For the deletemin and deletemax operations report which values were returned.
The lab is due by midnight Sunday.
