Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 04:34] – holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 19:20] (current) – holmesr
@@ Line 3: / Line 3: @@
 Statement 2.11 from the book says that "a sequence of O(n) priority queue operations can be used to sort a set of n numbers". This is because the set of numbers can be inserted into it with their value as their priority and then extracted in order of priority, resulting in their being in sorted order. I wondered when reading this, then, why we can not come up with a linear sort algorithm? I know I must be missing something but why is this not a linear sort?
-Regardless, we will use a heap to implement our priority queue. The heap is an array with an object at position i, its left child at 2i and its right child at 2i+1.
+Regardless, we will use a heap to implement our priority queue. It helps to visualize a heap as a balanced binary tree with a root node and each node having two or fewer child nodes. The heap will be represented in an array with an object at position i, its left child at 2i and its right child at 2i+1. Importantly, the value at any child node can not be less than the object at its own parent node.
+Maintaining the heap order in an array during additions and deletions requires special algorithms that rearrange the nodes and allow for insertion and deletion in O(log n) time. First, to add an item to the heap, it is inserted into position n + 1 (for a heap of size n) and then Heapify-up is called. Heapify-up checks whether the recently inserted value is less than the value of it parent node and if so, it swaps the two and recursively calls itself. This maintains heap order by pushing lower values towards the top of the array. To delete an item in a heap and maintain heap order, the item at position n is placed in the array where the item to be deleted had been, and then Heapify-down is called. As one would expect, Heapify-down works in the opposite direction of Heapify-up by comparing a parent to its children and swapping the parent with the lower child if possible. This algorithm also calls itself recursively until heap order has been restored.
+Some important running times to note when implementing priority queues with heaps:
+  * ''StartHeap(N)'' initializes an array of size N in O(N) time
+  * ''Insert(H, v)'' inserts v into heap H using Heapify-up, for a heap of size n this takes O(n) time
+  * ''FindMin(H)'' Identifies the minimum element which is the root node using O(k) time
+  * ''Delete(H, i)'' deletes the element at position i using Heapify-down for O(log n) time
+  * ''ExtractMin(H)'' combines ''FindMin(H)'' and ''Delete(H, i)'' to delete the min in O(log n) time