Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:david:chapter2 [2011/01/25 20:41] – [2.5 - A More Complex Data Structure: Priority Queues] margoliesd | courses:cs211:winter2011:journals:david:chapter2 [2011/01/25 20:53] (current) – [2.5 - A More Complex Data Structure: Priority Queues] margoliesd |
|---|
| ====2.5 - A More Complex Data Structure: Priority Queues==== | ====2.5 - A More Complex Data Structure: Priority Queues==== |
| |
| An efficient algorithm can be improved by using a different kind of data structure. For the Stale Matching Problem, we used a priority que | An efficient algorithm can be improved by using a different kind of data structure. In a priority queue, all elements have an associated key or value, and the lower the value, the higher the priority. Operating systems use priority queues to determine which process gets to use the CPU. In a priority queue, an element can be added, deleted, and the highest priority item can be selected in O(logN) time. Priority queues can be implemented using a heap, which is visually like a "balanced" binary tree, but stored in memory as an array. The key/value of every element is be at least as large (higher priority) as its parent. A node's at array position i has its left child at array position 2i and right child at 2i+1. Adding a new element to the heap is O(logN) because we must Heapify-up the element after adding it to the end of the array. This implies we keep track of the number of elements in our heap, or we would need to iterate through the array every time. The highest priority item is simply the first element in the array, but to remove it, we need to fill in its gap with the last element in the array. Then we Heapify-down this element to maintain the heap, which takes O(logN) time. |
| | |
| | I give this section a readability of 7/10. |
