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