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 calls 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 k1 k2 k3:

• irreflexive property - k not less than k
• transitive property - if $ k_1 < k_2 $ and $ k_2 < k_3 $ then $ k1 < k_3 $

minimal key - the key for which $ k_{min} \leq k \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://charlesreid1.com:3000/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://charlesreid1.com:3000/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 9old 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:

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