- How long would it take to remove the log(n) smallest elements from a min-heap which contains n entries, using the
removeMin operation? Explain your answer.
- If I perform an inorder traversal of a binary search tree, the elements will be listed in ascending order. Is this true for a heap data structure? Why or why not?
- 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 tree as well as what it would look like if we stored it as an array.
- Sketch out an example of a red-black tree that is not an AVL tree. Explain why your diagram is not a valid AVL tree.
- 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.