Question 2: Heaps

A complete binary tree of height h has all the levels filled through level h-1, and the leaves on level h are filled left to right. In other words,

1. All nodes at level h-2 and above have 2 children each, and 2. When a node at level h-1 has children, all nodes to its left at the same level have 2 children each, and 3. When a node at level h-1 has one child, it is a left child

A max-heap is a complete binary tree with the following recursive definition: 1) empty OR 2) whose root contains a search key greater than or equal to the search key in each of its children, AND 3) whose subtrees are also heaps

For example, this first tree is a max-heap. This second tree is not. Consider the subtree rooted at 50.

Part 1

The idea behind inserting into a max-heap is 1) Create a new node at level h (in the appropriate spot) and store the new value there. Note that now you may no longer have a heap. 2) Then, compare this value with the value of its parent. Swap values if out of order. 3) Repeat this "bubble up" process until you have a heap again.

Draw a picture of the max-heap created by inserting the following data (insert each item, one at a time, in the order shown), starting with an empty max-heap: 10 5 8 15 3 12 14 20 9

Part 2

A very useful implementation for a max-heap is an array. The root is stored at index 0, and its children are stored at index 1 and 2. For any node at index i, its left child is at index [2*i + 1] and its right child is at index [2*i + 2] (note that this even works for the root). A size variable would hold how much data is in the array. [NOTE: A similar array-based implementation of a heap is described in Section 18.2 in the textbook. This implementation does not skip element 0 in the array. Which one do you think provides better performance?]

Draw what the array would look like for the heap you drew above.

Part 3

Implement (on paper) the method public void heapInsert(int o) to insert a piece of data into the array-based heap based on the algorithm above. [Note: Because this is a max-heap, and because we are using element 0 in the array, this code will not be the same as the code in the textbook. The goal is for you to think through the algorithm and create your own implementation.]

Assumptions: 1) The Heap class has instance variables size and int[] items. 2) Assume there is a method ensureCapacity() just like we had for our SimpleArrayList class.

Hint: If you have the index of a node ( e.g. index i ), the index of the parent is [(i - 1) / 2].

100 100 50 60 70 85 55 45 35 50 40 80