Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter2 [2018/01/28 19:54] – patelk
+++ courses:cs211:winter2018:journals:patelk:chapter2 [2018/01/28 20:18] (current) – [2.5 A More Complex Data Structure: Priority Queues] patelk
@@ Line 216: / Line 216: @@
 **The Problem**
   * Priority Queue: Elements have a priority value (key), and each time we need to select an element from S, we want to take the one with highest priority.
           - Set of elements S
@@ Line 224: / Line 223: @@
 **A Data Structure for Implementing a Priority Queue**
   * List: have a pointer to the min; adding new elements is easy, but extracting the minimum requires O(n) scan to find the new minimum
   * Sorted Array: binary search to find position of insertion + shifting all elements -> O(nlogn)
   * Sorted Doubly Linked List: insertions are O(1), but O(n) to find position of insertion
-__The Heap__ balanced binary tree; root + nodes with up to two children; key of any element is at least as large as the key of the parent node
+__The Heap:__ balanced binary tree; root + nodes with up to two children; key of any element is at least as large as the key of the parent node
   * For a heap with bound N, we can use an array
   * H[1] is the root
-  * leftChild(i) = 2i  // rightChild(i) = 2i+1
+  * leftChild(i) = 2i
+  * rightChild(i) = 2i+1
 **Implementing the Heap Operations**
-  * Identifying Minimal Element:** O(1)**
+  * Identifying Minimal Element: **O(1)**
   * Adding an Element: add element to the final position, then perform heapify-up recursively -> **O(logn)**
 {{:courses:cs211:winter2018:journals:patelk:heapify-up.png?nolink&400|}}
-  * Deleting an Element: move element w in position n to position i; key of element w may either be too small or too bit
+  * Deleting an Element: move element w in position n to position i; key of element w may either be too small or too bit -> **O(logn)**
   *   * If key is too small: use heapify-up to reestablish order
   *   * If key is too large: use heapify-down to sway the element with one of its children
 {{:courses:cs211:winter2018:journals:patelk:heapify-down.png?nolink&400|}}
+**Implementing Priority Queues with Heaps**
+  * __StartHeap(N):__ returns an empty heap that is set up to store at most N elements -> **O(n)**
+  * __Insert(H,v):__ inserts item v into heap H -> **O(logn)**
+  * __FindMin(H):__ identifies the min -> **O(1)**
+  * __Delete(H,i):__ deletes element in position i -> **O(logn)**
+  * __ExtractMin(H):__ identifies and deletes minimum key element -> **O(logn)**
+----
+==== Personal Thoughts ====
+This section was pretty straightforward and easy to follow. I think going over the concepts in class before reading this section of the textbook was helpful in clarifying things that maybe would have been otherwise confusing. I appreciated the summary of the operation run times as these can sometimes be difficult to recall.
+Readability: 9
+Interesting: 6