Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter2 [2018/01/30 04:42] – [2.4 – A Survey of Common Running Times] bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter2 [2018/01/30 04:54] (current) – [2.5 – A More Complex Data Structure: Priority Queues] bairdc
@@ Line 38: / Line 38: @@
 Overall, this section was pretty readable and interesting. I'd give it a 7/10. The one nagging question I have is why the total number of subsets of an n-element set is 2^n. This is probably a very simple question and basic answer, but for some reason I'm having a hard time visualizing it.
+===== 2.5 – A More Complex Data Structure: Priority Queues =====
+The goal with a priority queue is to implement a data structure with n elements so that elements can be added and deleted, and the minimum selected, all in O(logn) time. You could use a list, but after removing the minimum, there needs to be a scan of all elements in O(n) time to find the new minimum. Also you couldn't use binary search for a linked list, and in an array you'd have to shift values in O(n) for the constant time insertions. A heap combines the benefits of an array and list to best work with a priority queue. Left children of i are 2i and right children of i are 2i+1. For a heap, it takes O(1) time to identify the minimum element. The two algorithms for balancing are Heapify-up and Heapify-down. Both run in O(logn) time. One involves swapping values up the heap (heapify-up) and the other involves swapping values down the heap (heapify-down), which need arises when a value is deleted.
+Balancing algorithms are shown below:
+<code>
+Heapify-down(H, i):
+  n = length(H)
+  if 2i > n then
+    Terminate with H unchanged
+  else if 2i < n then
+    left=2i and right=2i+1
+    j be index that minimizes key[H[left]] and key[[H[right]]
+  else if 2i = n then
+    j=2i
+  if key[H[j]] < key[H[i]] then
+    swap array entries H[i] and H[j]
+    Heapify-down(H, j)
+</code>
+<code>
+Heapify-up(H, i):
+  if i > 1 then
+    j=parent(i)=floor(i/2)
+    if key[H[i]] < key[H[j]] then
+      swap array entries H[i] and H[j]
+      Heapify-up(H, j)
+</code>
+This section was very readable and I would give it a 10/10 on readability and interestingness. I have no lingering questions after reading through the section.