**************************************
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 :math:`\Theta(\log n)`

  * enqueue: :math:`\Theta(\log n)`, add to the end and percolate up
  * dequeue: :math:`\Theta(\log n)`, replace the root with the last element and
    percolate down
  * percolate up: :math:`\Theta(\log n)`
  * percolate down: :math:`\Theta(\log n)`
  * heapify:

    - :math:`\Theta(n)` - repeated percolate down on all internal nodes
    - :math:`\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
  * :math:`\Theta(n \log n)`