Priority Queues Study Guide

Definitions and Variations

Definitions

priority queue - a FIFO collection of prioritized elements that allows arbitrary insertion and removal of the element with highest priority

composition design pattern - a class that wraps multiple other classes or pieces of data

comparison rule - the criteria <= used to determine which priority queue element is the minimum; e.g., in Java you can pass in a comparator at construction

total order relation - a less than or equal to <= relation that satisfies three properties for three keys k1 k2 k3:

• comparability property - either $k_{1}\leq k_{2}$ or $k_{2}\leq k_{1}$ must be true
• antisymmetric property - if $k_{1}\leq k_{2}$ and $k_{2}\leq k_{1}$, then $k_{1}=k_{2}$
• transitive property - if $k_{1}\leq k_{2}$ and $k_{2}\leq k_{3}$, then $k_{1}\leq k_{3}$

These three properties, in turn, imply the reflexive property - $k\leq k$.

strict weak order - a weaker less than relation that satisfies two properties for three keys $k_{1},k_{2},k_{3}$:

• irreflexive property - k not less than k
• transitive property - if $k_{1}<k_{2}$ and $k_{2}<k_{3}$ then $k_{1}<k_{3}$

minimal key - the key for which $k_{min}\leq k\quad \forall k\in K$, where K is the set of all keys in the queue

comparator - object external to the keys it compares

binary heap - data structure that stores elements hierarchically by value, smallest at the root; guarantees all nodes are greater than their parents.

compete binary tree - binary tree in which each level has maximum number of nodes possible (breadth-first filling in)

heap ordering property - tree property guaranteed by binary heap; value of a node n is always greater than the value of its parent

up-heap bubbling - upward movement of newly inserted element via swaps, post insert

down-heap bubbling - downward movement of rearranged elements via swaps, post remove

amortization - distributing the cost of an operation in a more even way by spreading it out over a fixed period of times or number of operations

ADTs and Interfaces

Priority Queue ADT

Standard priority queue class adt:

• insert
• min
• removeMin
• size
• empty

Java API

The Java API implements a PriorityQueue object. It implements the following methods:

• add
• peek
• remove
• clear
• size
• empty

Important: constructor that takes comparator has the method signature public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) so don't forget the initial capacity int argument.

Java API docs: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Implementations

Unsorted List Priority Queue:

• Item class:
  • key
  • value
  • constructor
  • get/set key/value
  • comparison by key - requires comparable keys and/or comparable nodes and/or key comparator
• Priority queue class:
  • add - adds to end
  • find minimum - walks the list and looks for the minimum
  • delete - just deletes the node/item from the list

Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UnsortedPQ.java

Sorted List Priority Queue:

• Item class:
  • key
  • vlaue
  • constructor
  • get/set key/value
  • key comparison capability (key comparator best)
• Priority queue class:
  • add to correct position
  • find minimum always first element
  • delete just deletes node
  • maintenance operations required

Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

Heap Priority Queue:

• Heap
• Link-based heap uses binary tree
  • Array based heap is stored directly, no need for external object
• Heap priority queue:
  • heap, or data[], depending on implementation
  • upheap private utility method
  • downheap private utility method
  • swap private utility method
  • public add/min/removeMin methods

Algorithms for Operations

Heap Priority Queue

min method:

• deal with empty case
• return root of heap (data[0] if array)

remove min method:

• deal with empty case
• swap root and last node
• remove last node (old root)
• down-heap new node

add(e) method:

• add item to last heap position
• upheap new item

access and navigation:

• parent of node
• left node
• right node
• has left node
• has right node

swap(i,j) method:

• temp = i
• i = j
• j = temp

upheap bubbling(j) method:

• deal with root case
• start with node j's parent
• if node j < parent of j,
  • swap(j, parent)
  • upheap(parent)

downheap bubbling(j) method:

• if j has left:
  • smallest child is left
  • if j has right:
    • if right < left,
      • smallest child is right
  • if small child < node j,
    • swap(j, small child)
    • downheap(small child)

construct/heapify (note: see Heap Sort for fast construction of heaps):

• start at parent of last node
• for j in range start to 0:
  • downheap node j

algorithm: in-place sorting

• For array-based collections, can sort in-place with a heap sort
• Walk through the elements of the collection being sorted and construct a heap as you go (up-heap bubbling as we add)
• This will be a max-oriented heap, so use the negative of the regular key, or transform them into some kind of inverse-ordered key space
• Divide original collection into the front (heap elements) and the rear (sorted elements)
• Now as we remove max items from the heap, we add them to the end, in the sorted portion (down-heap bubbling as we remove)
  • Create heap
  • Walk through collection, adding elements to heap
  • Remove max item (at root) from heap and add to back of collection

Complexity and Cost

Big O Complexity Table

Big-O Complexity of Lists
	Unsorted Priority Queue	Sorted Priority Queue	Heap Priority Queue	Array-Based Heap PQ
size	O(1)	O(1)	O(1)	O(1)
empty	O(1)	O(1)	O(1)	O(1)
add	O(1)	O(n)	O(log n)	O(log n) amortized
removeMin	O(n)	O(1)	O(log n)	O(log n) amortized

OOP Principles

Composition:

• Composition design pattern creates classes that wrap data - implement the corresponding comparison operators using a comparator or extending comparable
• As the priority queue type is further adapted, you can further adapt the utility classes
• Example: public Locator class wraps private Item class; locator adds extra fields, implements fewer methods, simplifies method calls, etc.