Chapter 4: Priority Queue and Heap Sort

Priority Queue

• Not a queue, but a set of elements each with a priority
• Add in any order and remove in order of priority
  • Max first
  • Min first
• Behaviors
  • enqueue
  • dequeue
  • isEmpty
• Implementations
  • Unsorted array
  • Sorted array
  • Unsorted linked-list
  • Sorted linked-list
  • Heap
• Applications
  • Sorting
  • Find the n largest elements
  • Event-driven simulation
  • Huffman coding
  • Dijkstra’s algorithm
  • A* search

Heap

Our Binary Heap Visualizer demonstrates heap insertion, removal, and the tree/array relationship; use the course notes below for the separate heapsort procedure.

• Behaviors

  • add (put, insert)
  • remove (get, delete)
  • percolate up (swim, bubble)
  • percolate down (sink)
  • heapify (build heap)

• Complexity

  Mostly determined by the depth of the tree which is $\Theta(\log n)$

  • enqueue: $\Theta(\log n)$, add to the end and percolate up
  • dequeue: $\Theta(\log n)$, replace the root with the last element and percolate down
  • percolate up: $\Theta(\log n)$
  • percolate down: $\Theta(\log n)$
  • heapify:
    • $\Theta(n)$ - repeated percolate down on all internal nodes
    • $\Theta(n \log n)$ - repeated add

• Heap sort

  • Build a heap from the array
  • Repeatedly swap the root with the last element of the unsorted section and percolate down
  • $\Theta(n \log n)$