Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/29 23:33] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:45] (current) – [2.5.4 Comments] ahmadh
@@ Line 105: / Line 105: @@
 We could use a list to implement a priority queue, with a pointer labeled //Min// to the one with minimum key. This makes adding new elements easy, but extraction of the minimum hard. Specifically, finding the minimum is quick--we just consult the //Min// pointer--but after removing this minimum element, we need to update the //Min// pointer to be ready for the next operation, and this would require a scan of all elements in O(n) time to find the new minimum.
+To get better running times for its operations, we can use a heap for the implementation of a priority queue. The heap data structure combines the benefits of a sorted array and list for purposes of this application. Conceptually, we think of a heap as a balanced binary tree. The tree will have a root, and each node can have up to two children, a left and a right child. The keys in such a binary tree are said to be in heap order if the key of any element is at least as large as the key of the element at its parent node in the tree.
+=== 2.5.2.1 Implementing a Heap ===
+We can use an array H to represent a heap if we know of a upper bound //N// of the number of elements, or nodes, that would ever be in the heap at a given time. H[1] will always correspond to the root node, and for any node at position i, the left child and the right child of the node are at positions 2i and 2i+1 respectively.
+=== 2.5.2.2 Implementing the Heap Operations ===
+The heap element with smallest key is at the root, so it takes O(1) time to identify the minimal element.
+First consider adding a new heap element v, and assume that our heap H has n < N elements so far. Now it will have n+1 elements. To start with, we can add the new element v to the final position i=n+1, by setting H[i]=v. Unfortunately, this does not maintain the heap property, as the key of element v may be smaller than the key of its parent. So we now have something that is almost-a-heap, except for a small "damaged" part where v was pasted on at the end. We can use the following algorithm, Heapify-up, to fix this broken heap:
+	Heapify-up(H, i):
+	   If i > 1 then
+	      let j = parent(i) = [i/2]
+	      If key[H[i]] < key[H[j]] then
+	         swap the array entries H[i] and H[j]
+	         Heapify-up(H, j)
+	      Endif
+	   Endif
+Thee procedure Heapify-up(H,i) fixes the heap property in O(log i) time, assuming that the array H is almost a heap with the key of H[i] too small. Using Heapify-up we can insert a new element in a heap of n elements in O(log n) time.
+We can also implement the operation Delete(H, i), which will delete the element in position i. Assume the heap currently has n elements. After deleting the element H[i], the heap will have only n-1 elements; and not only is the heap-order property violated, there is actually a "hole" at position i, since H[i] is now empty. So as a first step, to patch the hole in H, we move the element w in position n to position i. After doing this, H at least has the property that its n - 1 elements are in the first n-1 positions, as required, but we may well still not have the heap-order property. We can fix this using a similar algorithm, called Heapify-down:
+	Heapify-down(H, i):
+	   Let n = length(H)
+	   If 2i > n then
+	      Terminate with H unchanged
+	   Else if 2i < n then
+	      Let left = 2i, and right = 2i + l
+	      Let j be the index that minimizes key[H[left]] and key[H[right]]
+	   Else if 2i = n then
+	      Let i = 2i
+	   Endif
+	   If key[H[j]] < key[H[i]] then
+	      swap the array entries H[i] and H[j]
+	      Heapify-down (H, k)
+	   Endif
+All the steps in Heapify-down, except the recursive call to itself, are O(1) operations. The recursive call is O(log n). Therefore, Heapify-up and Heapify-down are O(log n) algorithms, allowing us to add to or delete from a heap in log n time.
+==== 2.5.3 Operations for Priority Queues ====
+Below is a summary of the operations that we can use with a priority queue implemented with a heap:
+  * StartHeap(N): O(N) time
+  * Insert(H, v): O(log n) time
+  * FindMin(H): O(1) time
+  * Delete(H, i): O(log n) time
+  * ExtractMin(H): O(log n) time
+==== 2.5.4 Comments ====
+The motivation for priority queues was pretty intuitive. The description of heaps and the operations that can be performed on heaps was easy to read and follow, since heaps look similar to binary search trees. I found the application of using heaps to implement a priority queue very interesting--it looked like a very effective way of getting a better runtime of O(log n) on heap operations, as opposed to the O(n) that list-based implementations offer. The logic behind the Heapify-up and Heapify-down algorithms was easy to understand as well. Overall, I feel like I enjoyed reading about how priority queues work under the hood.
+I had a question though: is there a reason why one would prefer using priority queues to sort a list of items, as opposed to something like Mergesort, since both run in O(n log n) time, and MergeSort is arguably less complicated to implement (compared to implementing a heap and then using it to represent a priority queue)?