Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:shannon:chapter2 [2014/01/20 19:52] – nollets | courses:cs211:winter2014:journals:shannon:chapter2 [2014/01/20 22:35] (current) – nollets | ||
|---|---|---|---|
| Line 45: | Line 45: | ||
| I would give this section a 8/10 because it was incredibly helpful and created a place where I can easily reference needed runtimes. | I would give this section a 8/10 because it was incredibly helpful and created a place where I can easily reference needed runtimes. | ||
| + | |||
| + | =====Section 2.5: A More Complex Data Structure: Priority Queues===== | ||
| + | |||
| + | The priority queue is a data structure that organizes items in an array-like structure where each item has a priority value. When we remove items from the list we take the one with the highest priority first. However, sorting algorithms involved with priority queues run in O(n^2) time and we would like to be able to have O(n logn) time. So we implement a priority queue with a heap. The heap is a data structure similar to a binary search tree. The heap allows us to create a sorting algorithm in O(n logn) time. It uses two algorithms, Heapify-Up and Heapify-Down, | ||
| + | The algorithms used in this section are Heapify-up (page 61) and Heapify-down (page 63). Both algorithms are O(n logn) and allow us to run a sorting algorithm in O(n logn) time. | ||
| + | I am still a little confused on why we just don’t call the heap a priority heap. The distinction between a type of heap and then a priority implemented with a heap. | ||
| + | I would give this section an 8/10. It was interesting and was very easy to follow. It also helped reinforce the ideas that we covered in class. | ||
| + | |||
