CISC220 F2014 Lab7
From class_wiki
Lab #7
1. Written problems
- (1 point) What are the minimum and maximum number of leaves in a binary heap of height h, where a single-node tree is height 1? Show your reasoning.
- (2 points)
- (a) Draw the tree after each insertion of the following integer keys into a max heap, both before and after upheaping: 80, 40, 30, 60, 81, 90, 100, 10.
- (b) Now removeMax() is called on the tree just created. Show the tree after each step of the process of removeMax(), before and after downheaping. Clearly label or mark what is going on for both (a) and (b).
- (2 points) Write a C++ function int removeMax() for a heap that is represented in array form (root at index 1, etc.). Assume the array is called H and that int leftChild(int i), int rightChild(int i), and int parent(int i) functions are defined which return the array index of those nodes given the index of node i.
2. Submission
- Make a PDF file <Your Name>_Lab7_README.pdf with your answers to the written exercises
- No need to compress or archive the PDF, since that's all you're turning in.
- Submit it in Sakai by midnight at the end of Thursday, October 30
