COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Review Questions — Priority Queues and Heaps

Priority Queues

1. Compare the running times of the operations of priority queues implemented with an unsorted list and with a sorted list. Assume that the lists are implemented by a doubly linked list.

Heaps

1. What are the minimum and maximum numbers of nodes in a partially ordered tree (or "heap") of height h? (Express your answer in terms of h.)

2. Draw the partially ordered tree represented by the following linear representation of a heap. (In the terminology used by Goodrich and Tamassia, that would be "Draw the heap represented by the following array-list binary tree representation.") Then, in a separate diagram, draw the partially ordered tree ("heap") that results from inserting 'D' into the tree, assuming the priority relation is alphabetical order.

   A   F   B   F   G   C   R   G   N   M

3. Is there a partially ordered tree ("heap") storing seven distinct elements such that a preorder traversal of the tree yields the elements in sorted order? If so, draw it. If not, explain why it is not possible.

Heapsort

1. Heapsort operates in two phases. In the first phase, it transforms the (unordered) input array into a linear heap by bottom-up heap construction. (Assuming that we desire the array to be sorted in non-decreasing order, we need to make it a max-heap.) In the second phase, heapsort essentially calls removeMax() (or removeMin() with a reverse comparator) repeatedly on the priority queue corresponding to the max-heap, moving the value removed to the start of a 'sorted' zone at the end of the array, while the 'heap' zone shrinks.

   Assume that the following array shows the state of the input array after it has been transformed to a heap:

   1	2	3	4	5	6	7	8	9	10	11	12
   19	10	18	9	5	15	4	6	1	2	3	9

1. Draw the partially ordered tree (heap) represented by the linear heap ("array-list binary tree representation") above.

2. Show the next three stages in the progress of heapsort. One "stage" means doing a removeMax() (which also restores the partially ordered tree property ["heap-order property"] of the heap) and putting the removed value in the correct place in the "sorted" zone.