Discussion 13 handout

Group members (names & NetIDs)

Objectives

Binary heaps

Push

Consider a min-heap of integers (where each element’s priority is its own value). The heap is stored as the first 11 elements of int[] b, where b.length is 13 (remember the array implementation of a heap). Here are the current values in b (a ? indicates an element whose value is not logically contained in the heap; the heap currently has size 11):

{ 4, 5, 7, 6, 8, 8, 9, 7, 7, 8, 9, ?, ? }

Draw the complete binary tree representation of this heap. Label each node with its index in the array.

Add the value 3 to the end of the heap, then bubble it up to its appropriate location. Draw the resulting tree.

Write the sequence of values contained in b representing the above tree.

Pop

Consider a min-heap of integers (where each element’s priority is its own value). The heap is stored as the first 12 elements of int[] b, where b.length is 15. Here are the current values in b (a ? indicates an element whose value is not logically contained in the heap; the heap currently has size 12):

{ 2, 3, 4, 7, 6, 5, 6, 8, 9, 8, 9, 7, ?, ?, ? }

Draw the complete binary tree representation of this heap. Label each node with its index in the array.

Pop the next element from the heap, then perform the necessary operations to restore the heap invariants. Draw the resulting tree.

Write the sequence of values contained in b representing the above tree.

What value should be returned by pop() after completing the above operations?

Heapsort: Obtaining heaps

A common use case of binary heaps is Heapsort. Heapsort sorts its input by first shuffling the elements in the array to establish a heap’s order invariant, then repeatedly performing a heap’s “remove” operation to yield its elements in order. The slides from Lecture 27 outlined two ways of performing the first step, which we will explore here:

“Heapify”

First, we will go into more detail about Option 2: “Heapify”. In this activity, we will be using max-heaps, since extracting from max-heaps will give us an array sorted in ascending order.

In class and in this activity, we use “heapify” to mean the operation of building a heap from the elements of an arbitrary array in a bottom-up manner, as we will walk through in this discussion. The term “heapify” is alternatively used by some sources to refer to the “bubble down” procedure discussed in class, which the textbook calls “reheap”.

A semiheap is a binary tree (or a subtree) where the left and right subtrees are both heaps. Conceptually, “heapify” first interprets the input as a binary tree (not a binary heap), and works bottom-up to turn semiheaps into heaps. Let’s trace through a couple of steps of “heapify”.

Consider an array of integers (where each element’s priority is its own value). The elements are stored in int[] b, where b.length is 9. Here are the current values in b:

{ 1, 3, 5, 8, 4, 7, 2, 9, 6 }

The complete binary tree representation of this array looks like this:

Heap represented by { 1, 3, 5, 8, 4, 7, 2, 9, 6 }

Label each node in the above tree with its index in the array.

Let’s first identify the heaps and semiheaps in the tree. Draw outlines around each semiheap larger than a node in the above tree, and annotate the array below with three regions: “heap root”, “semiheap root”, and “neither”. How many semiheaps did you find?

{  1,  3,  5,  8,  4,  7,  2,  9,  6  }

Now, let’s make a semiheap into a binary heap through the “bubble-down” procedure. If you identified multiple semiheaps, resolve the bottom-rightmost semiheap (the rightmost semiheap on the bottom level). Draw the resulting binary tree.

What are the remaining semiheaps? Draw dotted lines around each semiheap in your new tree. Write the array representation of the tree below, and annotate with three regions: “heap root”, “semiheap root”, and “neither”.

Did a node that was previously in the “neither” category switch categories? Why/why not?

Let’s resolve the next semiheap, which is again the bottom-rightmost semiheap. Write the array representation of the tree below, and annotate with three regions: “heap root”, “semiheap root”, and “neither”.

This time, did a node that was previously in the “neither” category switch categories? Why/why not?

Repeat this process until all semiheaps have become heaps. Write the sequence of values contained in b representing the created heap. How many swaps did you make in total?

“Add each element”

Let’s similarly trace the “add each element” strategy on the same array that we traced through the “heapify” strategy on earlier:

Compare your trace of “add each element” against your trace for “heapify”. How many steps did you take? Did you have the same number of swaps?