Module 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

• 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)\)