Section 6.4 of Levitin, 3e on "Heaps and Heap Sort" is just chock-full of material. Plus, I have given you complete C++ code for all of Levitin's functions and those discussed in exercises 2 and 5. (This is all in P:\Public\CmpSc 465 Spring 2013\heaps.) The natural question is, "What should you concentrate on?"

  1. Know how to write (in C++) the 3 parameter version of the isHeap function.

  2. Know how to trace heapBottomUp by showing the result of each call made to siftDown. You can check your work by running code that I have provided in P:\Public\CmpSc 465 Spring 2013\heaps.

  3. Know how to trace heapTopDown by showing the result of each call made to siftUp.
    Check your work by running my code.

  4. Know how to write and evaluate an expression for the number of key comparisons done by heapBottomUp for a full tree.

  5. Know how to write and evaluate an expression for the number of key comparisons done by heapTopDown for a full tree.

  6. Given the function siftDown, know how to write heapBottomUp.

  7. Given the function siftUp, know how to write heapTopDown.Given the function siftDown, know how to write sortHeap.

  8. Know how to analyze sortHeap's worst case.

  9. Explain how a max (min) heap can be used as a priority queue. For this, I have given you code in P:\Public\CmpSc 465 Spring 2013\priority_queues.