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