Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:15] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:45] (current) – [2.5.4 Comments] ahmadh
@@ Line 116: / Line 116: @@
 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.
+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)?