Differences

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

--- courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 19:17] – holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_2.5 [2018/01/29 19:20] (current) – holmesr
@@ Line 8: / Line 8: @@
 Some important running times to note when implementing priority queues with heaps:
-* 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
+  * ''StartHeap(N)'' initializes an array of size N in O(N) 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
+  * ''Insert(H, v)'' inserts v into heap H using Heapify-up, for a heap of size n this takes O(n) time
-* ExtractMin(H) combines FindMin(H) and Delete(H, i) to delete the min in O(log n) 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
+  * ''ExtractMin(H)'' combines ''FindMin(H)'' and ''Delete(H, i)'' to delete the min in O(log n) time