# Priority Queues Study Guide

### From charlesreid1

## Contents

# 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 or must be true**antisymmetric property**- if and , then**transitive property**- if and , then

These three properties, in turn, imply the **reflexive property** - .

**strict weak order** - a weaker less than relation that satisfies two properties for three keys :

**irreflexive property**- k not less than k**transitive property**- if and then

**minimal key** - the key for which , 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 right < left,
- 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.

# Flags

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |