8/25/2008 M KUMAR CSE5311 1CSE5311 Design and Analysis of Algorithms• This Class– Heaps and Heapsort?–QuickSort–Mergesort– Other Sorting Algorithms• At the end of the classBinary treesPriority queues and heapsQuicksortWorstcaseBestcaseMergesortRecurrences for Quicksortand MergesortFurther ReadingReference books on Algorithms8/25/2008 M KUMAR CSE5311 2Course Syllabus• Review of Asymptotic Analysis and Growth of Functions, Recurrences• Sorting Algorithms• Graphs and Graph Algorithms.• Greedy Algorithms: – Minimum spanning tree,Union-Find algorithms, Kruskal's Algorithm, – Clustering, – Huffman Codes, and – Multiphase greedy algorithms. • Dynamic Programming: – Shortest paths, negative cycles, matrix chain multiplications, sequence alignment, RNA secondary structure, application examples.•Network Flow: – Maximum flow problem, Ford-Fulkerson algorithm, augmenting paths, Bipartite matching problem, disjoint paths and application problems.• NP and Computational tractability: – Polynomial time reductions; The Satisfiability problem; NP-Complete problems; and Extending limits of tractability.• Approximation Algorithms, Local Search and Randomized Algorithms8/25/2008 M KUMAR CSE5311 3Heaps and HeapsortPriority TreesBuilding HeapsMaintaining HeapsHeapsort AlgorithmAnalysis of Heapsort AlgorithmFurther ReadingReference books on AlgorithmsSORTING ALGORITHMS8/25/2008 M KUMAR CSE5311 4Priority QueuesWhat is a priority queue?A priority queue is an abstract data type which consists of a set of elements. Each element of the set has an associated priority or keyPriority is the value of the element or value of some component of an elementExample :S : {(Brown, 20), (Gray, 22), (Green, 21)} priority based on name {(Brown, 20), (Green,21), (Gray, 22)} priority based on ageEach element could be a record and the priority could be based on one of the fields of the record8/25/2008 M KUMAR CSE5311 5ExampleA Student's record:Attributes : Name Age Sex Student No. MarksValues : John Brown 21 M 94XYZ23 75Priority can be based on name, age, student number, or marksOperations performed on priority queues,-inserting an element into the set-finding and deleting from the set an element of highest priority8/25/2008 M KUMAR CSE5311 6Priority QueuesPriority queues are implemented on partially ordered trees (POTs)• POTs are labeled binary trees• the labels of the nodes are elements with a priority• the element stored at a node has at least as large a priority as the elements stored at the children of that node• the element with the highest priority is at the root of the tree8/25/2008 M KUMAR CSE5311 7Example2421191314031072118/25/2008 M KUMAR CSE5311 8HEAPSThe heap is a data structure for implementing POT'sEach node of the heap tree corresponds to an element of the array that stores the value in the nodeThe tree is filled on all levels except possibly the lowest, which are filled from left to right up to a point.An array A that represents a heap is an object with two attributeslength[A], the number of elements in the array and heap-size[A], the number of elements in the heap stored within the array Aheap_size[A] ≤ length[A]8/25/2008 M KUMAR CSE5311 9HEAPS (Contd)The heap comprises elements in locations up to heap-size[A] .A[1] is the root of the tree.Position 1 2 3 4 5 6 7 8 9 10Value 24 21 19 13 14 3 10 2 7 11Given node with index i,PARENT(i) is the index of parent of i;PARENT(i) = i/2LEFT_CHILD(i) is the index of left child of i ; LEFT_CHILD(i) = 2×i;RIGHT_CHILD(i) is the index of right child of i; and RIGHT_CHILD(i) = 2×i +18/25/2008 M KUMAR CSE5311 10Heap PropertyTHE HEAP PROPERTYA[PARENT(i)] ≥ A[i]The heap is based on a binary treeThe height of the heap (as a binary tree) is the number of edges on the longest simple downward path from the root to a leaf.The height of a heap with n nodes is O (log n).All basic operations on heaps run in O (log n) time.8/25/2008 M KUMAR CSE5311 11202122232hn=20+21+22+23 + . . . + 2h=2h+1-1Number of nodes at different levels in a Binary Tree8/25/2008 M KUMAR CSE5311 12Heap AlgorithmsHEAPIFYBUILD_HEAPHEAPSORTHEAP_EXTRACT_MAXHEAP_INSERT8/25/2008 M KUMAR CSE5311 13HEAPIFYThe HEAPIFY algorithm checks the heap elements for violation of the heap property and restores heap property.Procedure HEAPIFY (A,i) Input: An array A and index i to the array. i =1 if we want to heapifythe whole tree. Subtrees rooted at LEFT_CHILD(i) and RIGHT_CHILD(i) are heapsOutput: The elements of array A forming subtree rooted at i satisfy the heap property.1. l ← LEFT_CHILD (i);2. r ← RIGHT_CHILD (i);3. if l ≤ heap_size[A] and A[l] > A[i]4. then largest ← l;5. else largest ← i;6. if r ≤ heap_size[A] and A[r] > A[largest]7. then largest ← r;8. if largest ≠ i9. then exchange A[i] ↔ A[largest]10. HEAPIFY (A,largest)8/25/2008 M KUMAR CSE5311 14724192114031013211247192114031013211242119131403107211242119714031013211LST; heapRST,heap8/25/2008 M KUMAR CSE5311 1572419 21 14 03 10 02 13 1124 7 19 21 14 03 10 02 13 1124 21 19 07 14 03 10 02 13 1124 21 19 13 14 03 10 02 07 11Running time of HEAPIFYTotal running time = steps 1 … 9 + recursive callT (n) = Θ (1) + T (n/2 )Solving the recurrence, we get T (n) = O (log n)8/25/2008 M KUMAR CSE5311 16BUILD_HEAPProcedure BUILD_HEAP (A)Input : An array A of size n = length [A], heap_size[A]Output : A heap of size n1. heap_size[A] ← length[A]2. for i ←length[A]/2 downto 13. HEAPIFY(A,i)18 12 54 75 64 25 42 78 9618 12 54 96 64 25 42 78 7518 12 54 96 64 25 42 78 7518 96 54 12 64 25 42 78 7518 96 54 78 64 25 42 12 7596 18 54 78 64 25 42 12 7596 78 54 18 64 25 42 12 7596 78 54 75 64 25 42 12 188/25/2008 M KUMAR CSE5311 1718125496642542757818125475642542967818 12 54 75 64 25 42 78 9618 12 54 96 64 25 42 78 758/25/2008 M KUMAR CSE5311 1818965412642542757818125496642542757818 12 54 96 64 25 42 78 7518 96 54 12 64 25 42 78 758/25/2008 M KUMAR CSE5311 1918965478642542751218 96 54 78 64 25 42 12 7596 18 54 78 64 25 42 12 759618547864254275128/25/2008 M KUMAR CSE5311 2096 78 54 18 64 25 42 12