- How long would it take to remove the log(n) smallest elements from a min heap which contains n entries, using the
remove_min operation? Explain your answer.
- At which positions of a min heap might the third smallest key be stored? It might be helpful to draw a picture of a min heap and highlight the positions.
- One of your classmates claims that a preorder traversal of a min heap will list its keys in increasing order. Draw an example of a min heap that proves them wrong.
- The following entries are inserted into a max heap in this order: 4, 14, 2, 5, 6, 1, 3, 0.
- Sketch a diagram showing the final state of the heap as a tree.
- Sketch out the array representation of the final state of the heap.
- Consider a situation in which a user has numeric keys and wishes to have a priority queue that is maximum-oriented. How could a standard (min-oriented) priority queue be used for such a purpose? You are not allowed to change the internals of the min-oriented priority queue.
- What is a location-aware entry in a priority queue? What problem does it solve?