DOC PREVIEW
MIT 6 006 - Priority Queues

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.006- Introduction to Algorithms Lecture 9 Prof. Piotr IndykMenu • Priority Queues • Heaps • HeapsortPriority Queue A data structure implementing a set S of elements, each associated with a key, supporting the following operations: increase_key(S, x, k) : insert element x into set S return element of S with largest key return element of S with largest key and remove it from S increase the value of element x’ s key to new value k (assumed to be as large as current value) insert(S, x) : max(S) : extract_max(S) : 41 46 49.1 56 time (mins) Lecture 3:Heap • Implementation of a priority queue (more efficient than BST) • An array, visualized as a nearly complete binary tree • Max Heap Property: The key of a node is ≥ than the keys of its children (Min Heap defined analogously) All my arrays start at index 1Heap as a Tree root of tree: first element in the array, corresponding to i = 1 parent(i) =i/2: returns index of node's parent left(i)=2i: returns index of node's left child right(i)=2i+1: returns index of node's right childOperations with Heaps insert, extract_max, heapsort produce a max-heap from an unordered array correct a single violation of the heap property in a subtree at its root build_max_heap : max_heapify : Heap OperationsMax_heapify • Assume that the trees rooted at left(i) and right(i) are max-heaps • If element A[i] violates the max-heap property, correct violation by “trickling” element A[i] down the tree, making the subtree rooted at index i a max-heapMax_heapify (Example)Max_heapify (Example)Max_heapify (Example) Time=? O(log n)Build_Max_Heap(A) Converts A[1…n] to a max heap Build_Max_Heap(A): for i=n/2 downto 1 do Max_Heapify(A,i) Time=? O(n) T(n)=2T(n/2)+O(log n) + Master TheoremHeap-Sort Sorting Strategy: 1. Build Max Heap from unordered array; 2. Find maximum element A[1]; 3. Swap elements A[n] and A[1]: now max element is at the end of the array! 4. Discard node n from heap (by decrementing heap-size variable) 5. New root may violate max heap property, but its children are max heaps. Run max_heapify to fix this. 6. Go to step 2.Heap-Sort Demo Swap A[10] and A[1] Max_heapify(A,1)Heap-SortHeap-SortHeap-Sort Sorting Strategy: 1. Build Max Heap from unordered array;Heap-Sort Sorting Strategy: 1. Build Max Heap from unordered array; 2. Find maximum element A[1]; 3. Swap elements A[n] and A[1]: now max element is at the end of the array!Heap-Sort Sorting Strategy: 1. Build Max Heap from unordered array; 2. Find maximum element A[1]; 3. Swap elements A[n] and A[1]: now max element is at the end of the array! 4. Discard node n from heap (by decrementing heap-size variable)Heap-Sort Sorting Strategy: 1. Build Max Heap from unordered array; 2. Find maximum element A[1]; 3. Swap elements A[n] and A[1]: now max element is at the end of the array! 4. Discard node n from heap (by decrementing heap-size variable) 5. New root may violate max heap property, but its children are max heaps. Run max_heapify to fix this.Heap-Sort Swap elements A[9] and A[1]Heap-Sort Max_Heapify(A,1)Heap-Sort Swap elements A[8] and A[1]Heap-Sort Running time: after n iterations the Heap is empty every iteration involves a swap and a heapify operation; hence it takes O(log n) time Overall O(n log


View Full Document

MIT 6 006 - Priority Queues

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Priority Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Priority Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Priority Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?