21.5 Exercises

Procedural

1. Represent the following heap as an array.

1. Consider the above heap. What range of values, when inserted, will cause the maximum number of swaps?

Problem 1

To convert a heap into an array, we simply read the values top-to-bottom and left-to-right. As such, the correct representation is [0, 5, 1, 8, 8, 6, 2].

Problem 2

Since 0 is currently the root, any value < 0 when inserted will have to swapped to from the bottom of the tree to the top, resulting in the maximum number of swaps. Thus, the range is $[-\infty, 0)$.

Metacognitive

1. Consider an externally-chained hashmap. If there are many hash collisions, what data structure would be most efficient in storing the key-value pairs at each bucket?

2. Consider an array sorted in descending order. Is this a valid heap? If so, which type: min-heap, or max-heap?

3. Suppose that we store the root of a heap at the 0th index in our array. For an arbitrary index k, compute the indices of its children and parent.

4. Explain how you would implement a stack using a priority queue.

Problem 1

An LLRB would be the best choice. Even if all items end up in same bucket, the LLRB will be balanced, resulting in a $O(\log n)$ search time where $n$ is the number of items in the bucket. Any other choice of data structure (linked list, array, binary search tree) could have linear search time in the word case within the bucket.

Note: Using an LLRB to store buckets requires that the keys be comparable.

Problem 2

An array sorted in descending order is a max-heap (the root is the maximum value, and values decrease in level order).

Problem 3

The children would be 2k + 1 and 2k + 2. The parent would be (k - 1) / 2 (note that this assumes integer division).

Problem 4

To implement a stack using a priority queue, keep a counter that increments each time you insert an item. Recently inserted items will always have higher priority, so they will be removed first.