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:11] – [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 229: | 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 |
| - | * k | + | * rightChild(i) = 2i+1 |
| **Implementing the Heap Operations** | **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)** | * Adding an Element: add element to the final position, then perform heapify-up recursively -> **O(logn)** | ||
| Line 255: | 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: | ||
| + | |||
| + | |||
