Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:30] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:45] (current) – [2.5.4 Comments] ahmadh
@@ Line 147: / Line 147: @@
 All the steps in Heapify-down, except the recursive call to itself, are O(1) operations. The recursive call is O(log n). Therefore, Heapify-up and Heapify-down are O(log n) algorithms, allowing us to add to or delete from a heap in log n time.
+==== 2.5.3 Operations for Priority Queues ====
+Below is a summary of the operations that we can use with a priority queue implemented with a heap:
+  * StartHeap(N): O(N) time
+  * Insert(H, v): O(log n) time
+  * FindMin(H): O(1) time
+  * Delete(H, i): O(log n) time
+  * ExtractMin(H): O(log n) time
+==== 2.5.4 Comments ====
+The motivation for priority queues was pretty intuitive. The description of heaps and the operations that can be performed on heaps was easy to read and follow, since heaps look similar to binary search trees. I found the application of using heaps to implement a priority queue very interesting--it looked like a very effective way of getting a better runtime of O(log n) on heap operations, as opposed to the O(n) that list-based implementations offer. The logic behind the Heapify-up and Heapify-down algorithms was easy to understand as well. Overall, I feel like I enjoyed reading about how priority queues work under the hood.
+I had a question though: is there a reason why one would prefer using priority queues to sort a list of items, as opposed to something like Mergesort, since both run in O(n log n) time, and MergeSort is arguably less complicated to implement (compared to implementing a heap and then using it to represent a priority queue)?