Comment on page

# 21.5 Exercises

- 1.Represent the following heap as an array.

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

- 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
`0`

th 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.

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.

Last modified 8mo ago