Heapsort

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Explain how a PriorityQueue can be used to sort a collection.
• Describe the efficiency of PriorityQueue based sort using Big-Oh notation.
• Define heapsort and explain how it relates to (and differs from) selection sort.
• Trace the operation of Floyd's heapify method, which builds the heap from the bottom up.
• Explain why we can ignore the leaves in the heapify process.
• Show there are ⌈ n/2 ⌉ leaves in a complete binary tree.
• Show Floyd's heapify is a linear-time operation.
• Explain and trace the in-place sorting stage of heapsort.
• Implement heapsort efficiently in Java.
• Use PriorityQueue to solve selection problems.

Starter code for this chapter.