Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/24 22:52] – [Section 4: A Survey of Common Running Times] lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter2 [2012/01/25 01:53] (current) – [Section 5: Priority Queues] lovellv
@@ Line 71: / Line 71: @@
 ===== Section 5: Priority Queues =====
+This section explains how to implement priority queue, a data structure that supports addition, deletion, and selection of the highest priority element.  Priority queues are useful for many things, including sorting a set of n numbers.
+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.  Finding the highest priority element in a heap is O(1) since the element with the smallest key is the root.  Adding and removing from a heap is O(logn) if we use Heapify-Up and Heapify-Down.
+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: 7