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 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.

Solution code

Solution code for this chapter.