# 21.5 Exercises
## Procedural
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?
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 `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.
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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook/21.-heaps-and-priority-queues/21.5-exercises.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.