6 006 Introduction to Algorithms Lecture 9 Prof Piotr Indyk Menu Priority Queues Heaps Heapsort Priority Queue A data structure implementing a set S of elements each associated with a key supporting the following operations insert S x insert element x into set S max S return element of S with largest key extract max S return element of S with largest key and remove it from S increase key S x k increase the value of element x s key to new value k assumed to be as large as current value Lecture 3 time mins 41 46 49 1 56 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 1 Heap 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 child OperationsHeap with Heaps Operations build max heap max heapify produce a max heap from an unordered array correct a single violation of the heap property in a subtree at its root insert extract max heapsort Max 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 heap Max 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 Theorem 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 6 Go to step 2 Heap Sort Demo Swap A 10 and A 1 Max heapify A 1 Heap Sort Heap Sort Heap 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 n
View Full Document
Unlocking...