Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:charles:chapter2 [2011/01/27 08:08] – gouldc | courses:cs211:winter2011:journals:charles:chapter2 [2011/01/27 08:20] (current) – gouldc |
|---|
| ===== 2.5 A More Complex Data Structure: Priority Queues ===== | ===== 2.5 A More Complex Data Structure: Priority Queues ===== |
| |
| A priority queue is a data structure that stores elements with priority values. Removing from a priority queue returns the element with the highest priority. This property can be applied to scheduling problems, like this one. Proposition 2.11 says a priority queue can sort n numbers in O(n) time. This is because it takes n steps to insert the numbers and n steps to remove elements from the PQ until it is empty. | Priority queues store elements with priority values. Removing from a priority queue returns the element with highest priority. Priority queues can be useful tools for scheduling problems, like the processes on a computer. Proposition 2.11 says a priority queue can sort n numbers in O(n) time. This is because it takes n steps to insert the numbers and n steps to remove the numbers (this is 2n in total, or O(n)). The section then explains the processes "heapify-up" and "heapify-down" which we received handouts for. The underlying heap structure of priority queues allows for insertion and deletion to occur in O(log n) time. |
