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 \nlt k $
• transitive property - if $ k_1 \lt k_2 $ and $ k_2 \lt k_3 $ then $ k1 \lt 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