Priority Queues Study Guide - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:45:30Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:45, 9 October 2019
Line 75:		Line 75:
	** delete - just deletes the node/item from the list		** 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		Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UnsortedPQ.java

	Sorted List Priority Queue:		Sorted List Priority Queue:
Line 90:		Line 90:
	** maintenance operations required		** maintenance operations required

	Link to implementation on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/SortedPQ.java		Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

	Heap Priority Queue:		Heap Priority Queue:

Admin: /* Heap Priority Queue */

2017-08-29T02:57:19Z

Heap Priority Queue

← Older revision		Revision as of 02:57, 29 August 2017
Line 150:		Line 150:
	*** downheap(small child)		*** downheap(small child)

	construct/heapify:		construct/heapify (note: see [[Heap Sort]] for fast construction of heaps):
	* start at parent of last node		* start at parent of last node
	* for j in range start to 0:		* for j in range start to 0:

Admin: /* Heap Priority Queue */

2017-08-29T02:47:30Z

Heap Priority Queue

← Older revision		Revision as of 02:47, 29 August 2017
Line 146:		Line 146:
	*** if right < left,		*** if right < left,
	**** smallest child is right		**** smallest child is right
	*** if small child < node j,		** if small child < node j,
	**** swap(j, small child)		*** swap(j, small child)
	**** downheap(small child)		*** downheap(small child)

	construct/heapify:		construct/heapify:

Admin: /* Definitions */

2017-08-29T00:08:22Z

Definitions

← Older revision		Revision as of 00:08, 29 August 2017
Line 16:		Line 16:
	These three properties, in turn, imply the '''reflexive property''' - <math>k \leq k</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~~:		'''strict weak order''' - a weaker less than relation that satisfies two properties for three keys <math>k_1, k_2, k_3</math>:
	* '''irreflexive property''' - k not less than k		* '''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>		* '''transitive property''' - if <math>k_1 < k_2</math> and <math>k_2 < k_3</math> then <math>k_1 < 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		'''minimal key''' - the key for which <math>k_{min} \leq k \quad \forall k \in K</math>, where K is the set of all keys in the queue

	'''comparator''' - object external to the keys it compares		'''comparator''' - object external to the keys it compares

Admin: /* Definitions and Variations */

2017-08-29T00:04:54Z

Definitions and Variations

← Older revision		Revision as of 00:04, 29 August 2017
Line 5:		Line 5:
	'''priority queue''' - a FIFO collection of prioritized elements that allows arbitrary insertion and removal of the element with highest priority		'''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		'''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		'''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

Admin: /* Heap Priority Queue */

2017-07-08T08:15:20Z

Heap Priority Queue

← Older revision		Revision as of 08:15, 8 July 2017
Line 114:		Line 114:
	* deal with empty case		* deal with empty case
	* swap root and last node		* swap root and last node
	* remove last node ~~9old~~ root)		* remove last node (old root)
	* down-heap new node		* down-heap new node

Line 154:		Line 154:
	* for j in range start to 0:		* for j in range start to 0:
	** downheap node j		** 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=		=Complexity and Cost=

Admin: /* OOP Principles */

2017-07-08T08:11:12Z

OOP Principles

← Older revision		Revision as of 08:11, 8 July 2017
Line 203:		Line 203:

	=OOP Principles=		=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=		=Flags=

Admin: /* Complexity and Cost */

2017-07-08T08:07:00Z

Complexity and Cost

← Older revision		Revision as of 08:07, 8 July 2017
Line 156:		Line 156:

	=Complexity and Cost=		=Complexity and Cost=

			==Big O Complexity Table==

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Lists
			\|-
			\|
			\|<br /><br />
			Unsorted Priority Queue
			\|<br /><br />
			Sorted Priority Queue
			\|<br /><br />
			Heap Priority Queue
			\|<br /><br />
			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=		=OOP Principles=

Admin: /* Algorithms for Operations */

2017-07-08T08:03:50Z

Algorithms for Operations

← Older revision		Revision as of 08:03, 8 July 2017
Line 104:		Line 104:

	=Algorithms for Operations=		=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 9old 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 small child < node j,
			**** swap(j, small child)
			**** downheap(small child)

			construct/heapify:
			* start at parent of last node
			* for j in range start to 0:
			** downheap node j

	=Complexity and Cost=		=Complexity and Cost=

Admin: /* Implementations */

2017-07-08T08:00:14Z

Implementations

← Older revision		Revision as of 08:00, 8 July 2017
Line 91:		Line 91:

	Link to implementation on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPQ.java		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=		=Algorithms for Operations=