Priority Queues and Heaps

Priority Queue: (Abstract) Collection of objects, each one with a comparable priority (totally ordered set)

• INSERT(Q, x, p): Add $x$ to $Q$, with priority $p$ (not unique)
• MAX(Q): Return max priority element
• EXTRACT-MAX(Q): Remove and return max priority element
• Max/min priority queue: A max priority queue is where the maximum value has the highest priority

Max-Heaps: Almost-complete binary trees, the last level is filled from the left

• Max Heap Order: Each node’s $p$ ≥ all its children’s $p$, but no ordering between siblings
• Stored as an array with no gaps, with root node at index 1. The $i$ node’s parent is $\frac{i}{2}$, left child is $2i$, right child is $2i+1$
• INSERT: $O(lg(n))$
  1. Insert the value at the end
  2. Recursively swap with parent if its parent’s priority is smaller
• EXTRACT-MAX: $O(lg(n))$ - Heapify
  1. Keep the max value (index 1) somewhere
  2. Override the start (index 1) with the last value of the array
  3. Recursively swap it with the largest children until no children is larger
• Build heap $\theta(n)$:
  1. Treat the array as a heap
  2. Run heapify from the first internal node (parents of leaves) to the root
• Heapsort $\theta(n \log n)$: Build heap, then extract max n-1 times.