Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:goldm:ch2 [2018/01/29 04:39] – goldm | courses:cs211:winter2018:journals:goldm:ch2 [2018/01/29 23:52] (current) – [2.5: A More Complex Data Structure: Priority Queues] goldm | ||
|---|---|---|---|
| Line 32: | Line 32: | ||
| ===== 2.5: A More Complex Data Structure: Priority Queues ===== | ===== 2.5: A More Complex Data Structure: Priority Queues ===== | ||
| - | The section goes over what a priority queue is, a set where each element has an associated key that allows it to be sorted by priority; the lower the key the higher the priority. An example of when this is useful is managing computer processes. It goes on to discuss an implementation that allows elements to be added, removed, and have the minimum element selected in logarithmic time. Having the aforementioned run times allows priority queue operations to sort a set. In order to implement the priority queue, the book uses a heap data structure. A heap structure implements the algorithm heapify up to insert elements in logarithmic time. | + | The section goes over what a priority queue is, a set where each element has an associated key that allows it to be sorted by priority; the lower the key the higher the priority. An example of when this is useful is managing computer processes. It goes on to discuss an implementation that allows elements to be added, removed, and have the minimum element selected in logarithmic time. Having the aforementioned run times allows priority queue operations to sort a set. In order to implement the priority queue, the book uses a heap data structure. A heap structure implements the algorithm heapify up to insert elements in logarithmic time. In order to remove the minimum element of the heap, we use ExtractMin. After doing this, if the key of the replacement element is too small, we use heapify up. If it is too big, we use heapify down. Both of these functions fix the heap in logn time. Thus, we can delete an element in logn time. The section then goes on to explain how we can implement the priority queue with a heap and discusses the necessary methods for doing so. Next, to add extra functionality to the queue, specifically, |
| + | |||
| + | This section is important in giving an example of how to use an appropriate data structure to efficiently implement a more complicated idea. I would like to see more and more examples of this throughout the text as I would consider it integral to developing useful algorithms in the real world, not just ones that look good on paper. | ||
| + | |||
| + | Overall, while important, as we have learned this all in class, I found the reading a little slow. Overall, it earns a 4/10. | ||
