Priority Queue

ADT: Operations in a PQ Utilizing a Heap

1. Insert

2. Get highest priority: O(1), it is the root of the tree

   • getMin or getMax

3. Remove Highest Priority: O(lgn) avg, O(n) worst, we must rearrange the tree

   • removeMax or removeMin
   • We must preserve the heap during insertion and removal. So, we swap the root with the right most array element (which is the last leaf in the tree) and swap the highest priority child to the root.

4. Insert: O(lgn) avg, O(n) worst, we must rearrange the tree

Heap Property

• A heap is a Binary Search tree such that:
  • root is of higher priority than rightChild and leftChild
  • There is no relation of priority between rightChild and leftChild
• Insert
  • Add a node to the next available spot
  • Push it up the tree until it supports the heap property
• Delete
  • Overwrite the root with the item in the last leaf
  • Delete the last leaf and push the root down to support heap property
• Array
  • Since a heap is a complete binary tree, we can represent it using an array
  • To find parent and children of node i:
    • parent(i) = floor((i-1)/2)
    • leftChild(i) = 2i+1
    • rightChild(i) = 2i+2
• Heap Sort
  • We take advantage of the heap property to sort
  • We "remove" the root node
    • not really though
    • we keep it in the same array but just don't access it
  • Runtime: Worst case O(nlgn)
  • In-Place: Yes
  • Stable: No
• Indirection
  • To make accessing elements in the PQ constant, we can make it indexible
  • Allows us to update objects