[[courses:cs211:winter2014:journals:alyssa:chapter_2.5]]
Trace:
Show page
AdminRecent ChangesSitemap

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2014:journals:alyssa:chapter_2.5 [2014/01/21 23:26] – hardnettacourses:cs211:winter2014:journals:alyssa:chapter_2.5 [2014/01/27 17:11] (current) – [Priority Queues] hardnetta
Line 1: Line 1:
-====== Priority Queues ======+====== Chapter 2.5: Priority Queues ======
  
 A priority queue is designed for applications in which elements have a priority value or key and each time we want to select an element from a set S, we want to take the one with the highest priority. Smaller keys represent higher priorities. Priority queues are good for managing real-time evens such as the scheduling of processes on a computer. Each process has a priority, but they do not arrive in order of their priorities. The running time of each operation of a priority queue is O(logn). Sorting a priority queue of n items takes O(nlogn) time. We use heaps to implement priority queues. It is possible to use a list (sorted or unsorted) but both of those data structures put sorting the queue in O(n^2) which is larger than O(nlogn). Conceptually, a heap is a balanced binary tree. The tree has a root, and each node can have up to 2 children, a left and a right child. The keys in the tree are said to be in heap order if they key of any element is at least as large as it key of its parent node. To represent a heap, we can either use pointers, with pointers pointing to the parent node and children, or we can use an array, where node i has a left child at 2i, a right child at 2i+1, and a parent at floor(i/2). Heaps have the smallest key at the root, so identifying the minimal element takes O(1) time. Adding and deleting elements is a bit more complicated. A priority queue is designed for applications in which elements have a priority value or key and each time we want to select an element from a set S, we want to take the one with the highest priority. Smaller keys represent higher priorities. Priority queues are good for managing real-time evens such as the scheduling of processes on a computer. Each process has a priority, but they do not arrive in order of their priorities. The running time of each operation of a priority queue is O(logn). Sorting a priority queue of n items takes O(nlogn) time. We use heaps to implement priority queues. It is possible to use a list (sorted or unsorted) but both of those data structures put sorting the queue in O(n^2) which is larger than O(nlogn). Conceptually, a heap is a balanced binary tree. The tree has a root, and each node can have up to 2 children, a left and a right child. The keys in the tree are said to be in heap order if they key of any element is at least as large as it key of its parent node. To represent a heap, we can either use pointers, with pointers pointing to the parent node and children, or we can use an array, where node i has a left child at 2i, a right child at 2i+1, and a parent at floor(i/2). Heaps have the smallest key at the root, so identifying the minimal element takes O(1) time. Adding and deleting elements is a bit more complicated.
courses/cs211/winter2014/journals/alyssa/chapter_2.5.1390346819.txt.gz · Last modified: 2014/01/21 23:26 by hardnetta
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0