Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:45] – ahmadh | courses:cs211:winter2018:journals:ahmadh:ch2 [2018/01/30 02:45] (current) – [2.5.4 Comments] ahmadh | ||
|---|---|---|---|
| Line 162: | Line 162: | ||
| 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. | 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, MergeSort is arguably less complicated to implement (compared to implementing a heap and then using it to represent a priority queue)? | + | 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)? |
