View source for 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 <math>k_1 \leq k_2</math> or <math>k_2 \leq k_1</math> must be true
* '''antisymmetric property''' - if <math>k_1 \leq k_2</math> and <math>k_2 \leq k_1</math>, then <math> k_1 = k_2</math>
* '''transitive property''' - if <math>k_1 \leq k_2</math> and <math>k_2 \leq k_3</math>, then <math>k_1 \leq k_3</math>

These three properties, in turn, imply the '''reflexive property''' - <math>k \leq k</math>.

'''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 <math>k_1 < k_2</math> and <math>k_2 < k_3</math> then <math>k1 < k_3</math>

'''minimal key''' - the key for which <math>k_{min} \leq k \forall k \in K</math>, 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 <code>public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)</code> 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

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=

=Complexity and Cost=

=OOP Principles=

=Flags=

{{StudyGuideFlag}}
[[Category:Study Guide]]

{{PriorityQueuesFlag}}