Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/22 03:27] – [Section 2.5 - A More Complex Data Structure: Priority Queues] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/22 04:03] (current) – [Section 2.4 - A Survey of Common Running Times] tobind
@@ Line 79: / Line 79: @@
 There are cases where one encounters running times that are asymptotically smaller than linear. Since it takes linear time just to read the input, these situations tend to arise in a model of computation where the input can be "queried' indirectly rather than read completely and the goal is to minimize the amount of querying that must be done. Example, binary search algorithm -> running time of //O(log n)//.
+I give this section a 8.5.
 ====== Section 2.5 - A More Complex Data Structure: Priority Queues ======
 **The Problem**
@@ Line 94: / Line 92: @@
 **A Data Structure for Implementing a PQ**
 We will use a data structure called a heap to implement a pq.  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, with a root and where 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. In other words,
-       Heap order: For every element //v//, at a node //i//, the element //w// at //i//'s parent satisfies key(//w//) ≤ key(//v//).
+       Heap order: For every element v, at a node i, the element w at i's parent satisfies key(w) ≤ key(v).
-Before we discuss how to work with a heap
+Before we discuss how to work with a heap, we need to consider what data structure should be used to represent it. We can use pointers: each node at the heap could keep the element it stores, its key and three pointers pointing to the two children and the parent of the heap node. We can avoid using pointers, however, if a bound //N// is known in advance on the total number of elements that will ever be in the heap at any one time. Such heaps can be maintained in an array //H// indexed by //i// = 1,...,//N//. We will think of the heap nodes as corresponding to the positions in this array. //H//[1] is the root, and for any node at position //i//, the children are the nodes at positions leftChild(//i//) = 2//i// and rightChild(//i//) = 2//i// + 1. The parent of a node at position //i// is at position parent(//i//) = [//i///2]. If the heap has //n// < //N// elements at some time, we will use the first //n// positions of the array to store the //n// heap elements and use length(//H//) to denote the number of elements in //H//. This representation keeps the heap balanced at all times.
+**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.
+Consider adding a new heap element //v// and assume that our heap  //H// has //n < N// elements so far. 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 heat property because the key of element //v// may be smaller than the key of its parent. We will use the procedure Heapify-Up to fix our heap. We will call the process recursively until the heap is fixed.
+     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
+To see why ^that works and eventually fixes the heap, let's look more fully at the not-fixed heap. Assume that //H// is an array and //v// is the element in position //i//. We say that "H is almost a heap with the key of //H[i]// too small" if there is a value α ≥ key(//v//) such that raising the value of key(//v//) to α would make the resulting array satisfy the heap property.
+-Heapify-up(//H, i//) fixes the heap property in //O//(log //i//) time. Using heapify we can insert a new element in a heap of //n// elements in //O(//log //n//) time.
+Consider deleting an element. After deleting an element at position //i//, there will be a "hole" at position //i//. So, as a patch, we move element //w// to position //i//. However, this probably isn't where //w// goes and violates the heap property...So, we run 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 + 1
+             Let j be the index that minimizes key[H[left]] and key[H[right]]
+         Else if 2i = n then
+             Let j = 2i
+         Endif
+         If key[H[j]] < key[H[i]] then
+             swap the array entries H[i] and H[j]
+             Heapify-down(H,j)
+         Endif
+Assume that //H// is an array and //w// is the element in postion //i//. We say that "H is almost a heap with the key of //H[i]// too big", if there is a value α ≤ key(//w//) such that lowering the value of key(//w//) to α would make the resulting array satisfy the heap property.
+- The procedure Heapifydown(//H,i//) fixes the heap property in //O//(log //n//) time, assuming that //H// is almost a heap with the key value of //H[i]// too big. Using Heapify-up or Heapify-down, we can delete a new element in a heap of //n// elements in //O//(log //n//) time.
+**Implementing PQs with Heaps**
+The heap data structure with the Heapify-down and Heapify-up operations can efficiently implement a pq that is constrained to hold at most //N// elements at any point in time. Here is a summary of operations we will use:
+  * StartHeap(//N//) returns an empty heap //H// that is set up to store at most //N// elements. This operation takes //O(N)// time, as it involves initializing the array that will hold the heap.
+  * Insert(//H, v//) inserts the item //v// into heap //H//. If the heap currently has //n// elements, this takes //O//(log //n//) time.
+  * FindMin(//H//) identifies the minimum element in the heap //H// but does not remove it. This takes //O//(1) time.
+  * Delete(//H, i//) deletes teh element in heap position //i//. This is implemented in //O//(log //n//) time for heaps that have //n// elements.
+  * ExtractMin(//H//) identifies and deletes an element with minimum key value from a heap. This is a combination of the preceding two operations and so it takes //O//(log //n//) time.
+I thought this section was really clear and helped my understanding a lot. On a readibility/interesting scale, I'd give it a 10.