Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/25 01:49] – [Section 5: Priority Queues] lovellv | courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/25 01:53] (current) – [Section 5: Priority Queues] lovellv | ||
|---|---|---|---|
| Line 73: | Line 73: | ||
| This section explains how to implement priority queue, a data structure that supports addition, deletion, and selection of the highest priority element. | This section explains how to implement priority queue, a data structure that supports addition, deletion, and selection of the highest priority element. | ||
| - | We can implement each queue operation in O(logn) time using a heap. A heap combines the benefits of a sorted array and a list. A heap can be thought of as a balanced binary tree where the key of a parent is always <= the keys of its children. | + | We can implement each queue operation in O(logn) time using a heap. A heap combines the benefits of a sorted array and a list. A heap can be thought of as a balanced binary tree where the key of a parent is always <= the keys of its children. |
| + | Thus, if we implement a priority queue with a heap, we get O(n) time to start the queue, O(logn) time to insert, O(1) time to find the minimum key, O(logn) time to delete and O(logn) to extract the value with minimum key. | ||
| + | Readability: | ||
