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:06] – 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 characteristic of priority queues is applicable to problems such as the scheduling of processes on a computer (weighted interval scheduling also comes to mind). Proposition 2.11 says a priority queue can sort n numbers in O(n) time. To do this you insert each number into the PQ (n steps) and then remove elements until the PQ is empty (n steps). | 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. |
