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 07:59] – 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 designed to store elements with priority values. It can add, delete, and select elements. When a priority queue is asked to "select" an element, it 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 comes to mind; see 1.2) | 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. |
