Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 19:19] – holmesr | courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 19:20] (current) – holmesr |
|---|
| Some important running times to note when implementing priority queues with heaps: | Some important running times to note when implementing priority queues with heaps: |
| |
| * ''StartHeap(N)'' initializes an array of size N in O(N) time | * ''StartHeap(N)'' initializes an array of size N in O(N) time |
| |
| * ''Insert(H, v)'' inserts v into heap H using Heapify-up, for a heap of size n this takes O(n) time | * ''Insert(H, v)'' inserts v into heap H using Heapify-up, for a heap of size n this takes O(n) time |
| |
| * ''FindMin(H)'' Identifies the minimum element which is the root node using O(k) time | * ''FindMin(H)'' Identifies the minimum element which is the root node using O(k) time |
| |
| * ''Delete(H, i)'' deletes the element at position i using Heapify-down for O(log n) time | * ''Delete(H, i)'' deletes the element at position i using Heapify-down for O(log n) time |
| |
| * ''ExtractMin(H)'' combines ''FindMin(H)'' and ''Delete(H, i)'' to delete the min in O(log n) time | * ''ExtractMin(H)'' combines ''FindMin(H)'' and ''Delete(H, i)'' to delete the min in O(log n) time |
