Priority Queues - Revision history

Admin: /* Heap */

2017-06-23T05:06:42Z

Heap

← Older revision		Revision as of 05:06, 23 June 2017
Line 128:		Line 128:

	<math>		<math>
	h \leq log{(n)}		h \leq \log{(n)}
	</math>		</math>

Line 135:		Line 135:
	</math>		</math>

	These two, plus fact that h is integer, imply		These two, plus fact that h is integer, imply h = floor( log( n ) )

	~~<math>~~h = \floor( \log( n ) )~~</math>~~

	===Inserting: Heap add and post-add===		===Inserting: Heap add and post-add===

Admin: /* Heap */

2017-06-23T05:06:14Z

Heap

← Older revision		Revision as of 05:06, 23 June 2017
Line 135:		Line 135:
	</math>		</math>

	These two, plus fact that h is integer, imply h = floor( log( n ) )		These two, plus fact that h is integer, imply

			<math>h = \floor( \log( n ) )</math>

	===Inserting: Heap add and post-add===		===Inserting: Heap add and post-add===

Admin: /* Priority queue interface */

2017-06-23T05:05:37Z

Priority queue interface

← Older revision		Revision as of 05:05, 23 June 2017
Line 22:		Line 22:
	Priority queue implementation details:		Priority queue implementation details:
	* insert(q,k) - given an item x with key k, insert into priority queue Q		* insert(q,k) - given an item x with key k, insert into priority queue Q
	* find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest ''key value''' of all elements in priority queue		* find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest '''key value''' of all elements in priority queue
	* delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max		* delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max

Admin: /* Basics of priority queues */

2017-06-23T05:05:09Z

Basics of priority queues

← Older revision		Revision as of 05:05, 23 June 2017
Line 12:		Line 12:

	The cost-effectiveness of inserting a new job into a queue, instead of constantly sorting and resorting and resorting again.		The cost-effectiveness of inserting a new job into a queue, instead of constantly sorting and resorting and resorting again.

			process of dating - example of application
			* as information is processed, removing, re-evaluating, reinserting samples into a queue

	===Priority queue interface===		===Priority queue interface===

Admin: /* Priority queue interface */

2017-06-23T05:04:43Z

Priority queue interface

← Older revision		Revision as of 05:04, 23 June 2017
Line 17:		Line 17:
	See also: [[Abstract Data Types]]		See also: [[Abstract Data Types]]

	Priority queue ~~implementations~~:		Priority queue implementation details:
	* insert(q,k) - given an item x with key k, insert into priority queue Q		* insert(q,k) - given an item x with key k, insert into priority queue Q
	* find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest ''key value''' of all elements in priority queue		* find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest ''key value''' of all elements in priority queue
	* delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max		* delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max
	* process of dating
	* as information is processed, removing, re-evaluating, reinserting samples into a queue

	===Implementations===		===Implementations===

Admin: /* Heap */

2017-06-18T03:32:02Z

Heap

← Older revision		Revision as of 03:32, 18 June 2017
Line 135:		Line 135:

	These two, plus fact that h is integer, imply h = floor( log( n ) )		These two, plus fact that h is integer, imply h = floor( log( n ) )

			===Inserting: Heap add and post-add===

			To add to a heap requires two actions:
			* Add a new node to the tree
			* Enforce the properties of a heap (arrangement by value)

			The heap add action requires creating a new heap node to store the key value pair (k,v).

			The compete binary property requires us to place the new node at the next available position on level h, or if the level h is filled, to place it in the left-most position of the next level.

			The post-insert action requires us to enforce the properties of a heap through a process called up-bubbling.

			If we have not inserted into an empty tree, we should compare the key of our new position p to p's parent, which we can denote q.

			If key p >= key q, heap-order property satisfied, algorithm terminates.

			If key p < key q, we need to restore heap-order property. We swap p and q.

			Heap-order property is now satisfied for position p, but needs to be satisfied for position q. Keep applying the routine as you move up the tree until you stop.

			The worst case is when a new node has been added that will become a new minimum for the heap: up-heap bubbling causing the new node to propagate all the way from its initial position, as a leaf node in the last level, to the root node. The worst-case cost is log(N).

			===Removing: Heap remove min and post-remove===

			The main method of the priority queue is a modification of the remove method of the queue ADT, the removeMin method. This removes the item at the root of the tree T. Once the root item is removed, however, the tree needs to be reconnected, which means removing is not as simple as an O(1) operation.

			We need to ensure that the tree stays a complete binary tree. To do that, we copy the very last item in the tree into the root node, and ensure (in reverse order this time, from the root working toward the leaf nodes) that the heap-order property is satisfied for each position.

			The post-removal algorithm to ensure heap-ordering is maintained is called down-heap bubbling. There are two cases for checking position p as we move down the tree and validate the values in the tree:
			* Position p has no right child, so let c be th left child of p.
			* Otherwise, p has both children, so let c be the child of p with minimal key.

			If key of p <= key of c, heap order property is satisfied, algorithm terminates.

			If key of p > key of c, we need to restore heap-order property, by swapping p and c.

			When p has two children, we must consider the smaller of the two children.

			Now that heap order is enforced for position p, we can move on to check position c. Continue swapping down T until no violation of the proeprty occurs. This is called down-heap bubbling.

	=Flags=		=Flags=

Admin: /* Notes */

2017-06-18T02:17:55Z

Notes

← Older revision		Revision as of 02:17, 18 June 2017
Line 33:		Line 33:

	Using a balanced binary search tree:		Using a balanced binary search tree:


			==Goodrich Chapter 9==

			===priorities and priority queues===

			Example: air-traffic control center deciding which flights to clear for landing among many approaching the airport

			Airport - example applications of stacks and queues

			A priority queue is a collection of prioritized elements that allows arbitrary element insertion, and the removal of the element with the highest priority.

			Most common for priorities to be expressed numerically, but any object can be used a a key so long as it supports comparison a < b

			Mapping: keys to integers or real numbers

			===Priority queue ADT===

			The abstract data type supports removal of one item, the item with the highest priority, so this is essentially a queue with a modified remove method:
			* P.add(k, v) - add an item with key k and value v into priority queue P
			* P.min() - peek minimum item - return an item (k,v) representing the key and value of item in priority queue P with minimum key, but do not remove the item.
			* P.remove_min() - remove minimum item - remove and return an item (k,v) that represents the key and value of minimum key in priority queue P

			===Implementation nodes===

			Several ways to concretely implement a priority queue. Two main ways:
			* sorted
			* unsorted

			OOP principles also apply to our implementation:
			* composition design pattern
			* composition - one object consisting of multiple parts
			* In this case, key and value
			* Other examples of composition: x,y point and nearest neighboring point, String item and count of occurrences

			===Unsorted implementation===

			Unsorted implementation: fast add operation, slow min/remove min operation

			For an unsorted array, can add anywhere so adding is O(1). Finding the minimum is an O(N) operation.

			Unsorted Priority Queue class: extends Priority Queue class

			Unsorted priority queue keeps track of things using a Positional List, which implements Doubly Linked List, which implements Linked List

			===Sorted implementation===

			Sorted has a slow add method and a fast minimum/remove minimum method.

			For a sorted array, add method needs to find the appropriate place to add the item in the sorted list, but it always knows where the minimum item is.

			The cost of inserting an item is worst-case O(N), since we have to at least traverse the array to reach the given node, and in the worst case that requires traversing N nodes. If we can randomly access nodes, however, we can find the minimum in O(log N) operations using a binary search.

			===Heap===

			The heap is a data structure offering some of the advantages of both a sorted and an unsorted array. (Trees have the advantage of sorting information hierarchically).

			In this case, the heap uses the tree level to sort information by value.

			'''Heap-Order Property:''' In a heap T, for every position p other than the root, the key stored at p is greater than or equal to the key stored at p's parent.

			As a consequence, a minimum key is always stored at the root of T. The min or remove min method therefore has an easy time.

			The heap must also satisfy an additional constraint: the heap must be complete.

			'''Complete Binary Tree Property:''' A heap T with height h is a complete binary tree if levels 0, 1, 2, ..., h-1 of T have the maximum number of nodes possible (namely, level i has 2^i nodes, for 0 <= i <= (h-1)) and the remaining nodes at level h reside in the leftmost positions possible.

			Basically, we fill in the levels, one level at a time, never skipping from one level to the next. This guarantees that the left and right subtrees of the root node cannot differ by more than 1 level.

			Proof:

			Heap height: a heap T with n entries has a height of floor(log(n)).

			This relies on the fact that IF the tree T is complete, there can only be one incomplete level at a time, so levels 0 through h-1 of the tree T must be complete. The number of nodes this represents is

			<math>
			n = 1 + 2 + 4 + ... + 2^{h-1} = 2^{h} - 1
			</math>

			the number of nodes in level h is somewhere between 1 and <math>2^h</math>, so this means

			<math>
			n \geq 2^h - 1 + 1 = 2^h
			</math>

			and

			<math>
			n \leq 2^h - 1 + 2^h = 2^{h+1} - 1
			</math>

			Taking the log of both sides of these inequallities, we see:

			<math>
			h \leq log{(n)}
			</math>

			<math>
			\log{(n+1)} -1 \leq h
			</math>

			These two, plus fact that h is integer, imply h = floor( log( n ) )

	=Flags=		=Flags=

Admin: /* Priority queue interface */

2017-06-03T06:59:51Z

Priority queue interface

← Older revision		Revision as of 06:59, 3 June 2017
Line 17:		Line 17:
	See also: [[Abstract Data Types]]		See also: [[Abstract Data Types]]

			Priority queue implementations:
			* insert(q,k) - given an item x with key k, insert into priority queue Q
			* find-min(q) or find-max(q) - return a pointer to the item with the smallest/largest ''key value''' of all elements in priority queue
			* delete-min(q) or delete-max(q) - remove item from priority queue whose key is min/max
			* process of dating
			* as information is processed, removing, re-evaluating, reinserting samples into a queue

			===Implementations===

			Priority queue complexity of operations, worst-case scenario?

			Using an unsorted array:

			Using a sorted array:

			Using a balanced binary search tree:

	=Flags=		=Flags=

Admin: /* Flags */

2017-06-03T06:50:33Z

Flags

← Older revision		Revision as of 06:50, 3 June 2017
Line 23:		Line 23:

	{{DataStructuresFlag}}		{{DataStructuresFlag}}

			[[Category:Queues]]

Admin: /* Priority queue interface */

2017-06-03T06:50:21Z

Priority queue interface

← Older revision		Revision as of 06:50, 3 June 2017
Line 17:		Line 17:
	See also: [[Abstract Data Types]]		See also: [[Abstract Data Types]]




			=Flags=

	{{DataStructuresFlag}}		{{DataStructuresFlag}}