Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:patelk:chapter2 [2018/01/28 20:03] – [2.5 A More Complex Data Structure: Priority Queues] 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** | **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. | * 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 | - Set of elements S | ||
| Line 230: | Line 229: | ||
| __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 | * For a heap with bound N, we can use an array | ||
| * H[1] is the root | * H[1] is the root | ||
| - | * leftChild(i) = 2i | + | * leftChild(i) = 2i |
| + | * rightChild(i) = 2i+1 | ||
| **Implementing the Heap Operations** | **Implementing the Heap Operations** | ||
| - | | + | |
| + | | ||
| * Adding an Element: add element to the final position, then perform heapify-up recursively -> **O(logn)** | * Adding an Element: add element to the final position, then perform heapify-up recursively -> **O(logn)** | ||
| Line 252: | Line 255: | ||
| * __Delete(H, | * __Delete(H, | ||
| * __ExtractMin(H): | * __ExtractMin(H): | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ==== 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: | ||
| + | Interesting: | ||
| + | |||
| + | |||
