# 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 ${\displaystyle k_{1}\leq k_{2}}$ or ${\displaystyle k_{2}\leq k_{1}}$ must be true
• antisymmetric property - if ${\displaystyle k_{1}\leq k_{2}}$ and ${\displaystyle k_{2}\leq k_{1}}$, then ${\displaystyle k_{1}=k_{2}}$
• transitive property - if ${\displaystyle k_{1}\leq k_{2}}$ and ${\displaystyle k_{2}\leq k_{3}}$, then ${\displaystyle k_{1}\leq k_{3}}$

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

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

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

minimal key - the key for which ${\displaystyle 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

• insert
• min
• removeMin
• size
• empty

## Java API

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

• 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.

# 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:
• 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:
• 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

# 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 item to last heap position
• upheap new item

• 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
• 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.