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