Description
Because of all the end of semester activities, this will be a two week lab. The topic is pairing heaps which are discussed in Section 12.6 (p. 602) in the text.
You will first work on building the structure and then must show that it has been built correctly. In order to build the initial structure you will need to code the insert operation.
Then, the deletemin operation and the two-pass merging must be implemented.
Mehrdad will describe the pairing heap structure at the beginning of the lab. The implementation of the structure is the part that will require the most work since you must determine how to link the nodes together in such a way as to be able to efficiently access the children of a node after a deletemin operation.
So for the first week, the goal is to get the structure correctly constructed and to verify its correctness. For the second week, you will finish the implementation.
Do to the test on Wednesday, the amount of work required to be turned in for the first part is very modest. You should work on next week’s part as you find time since that will require more work and because of stop day will be due on Thursday of next week.
To turn in:
week 1: the code you have written to build the pairing heaps. This is due on Saturday April 30.
week 2: the remainder of the coding of the structure and the deletemin and merging operations defined on it. Be sure to include a verification of the correctness of your structure. The proof of correctness will represent half of the lab grade. As noted above this is due on Thursday May 5.
