Heap Sort Priority Queues 1 PDF

Preview

Summary

By mingyu...

Description

Algorithm and Data Structure Analysis (ADSA) Lecture 9: Priority Queues/Heapsort

Algorithm and Data Structure Anal

1

Heap OperaEons: BuildHeap We can build a heap in a boJom up manner by running on successive subarrays Fact: for array of length n, all elements in range A[ n/2 + 1 .. n] are heaps (Why?) So: Walk backwards through the array from n/2 to 1, calling on each node. Order of processing guarantees that the children of node i are heaps when i is processed Algorithm and Data Structure Anal 3 9/07/14

BuildHeap

Algorithm and Data Structure Anal 4 9/07/14

BuildHeap() xample Work through example A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7} 4 1

3

2 14

16 8

9

7

Algorithm and Data Structure Anal 5 9/07/14

10

Analyzing BuildHeap ach call to takes O(lg n) Eme There are O(n) such calls (speci cally, n/2 ) Thus the running Eme is O(n lg n) Is this a correct asympto2c upper bound? Is this an asympto2cally 2ght bound?

A Eghter bound is O(n) How can this be? Is there a aw in the above reasoning? Algorithm and Data Structure Anal 6 9/07/14

Analyzing BuildHeap: Tight Theorem: The heap implementaEon realizes build in Eme O(n). Proof: There are at most 2l nodes of depth l (from root). A call of Heapify for each of these nodes takes Eme O(k l), k depth of the tree. Get total runEme by summing up l=0, …, k 1 Algorithm and Data Structure Anal 7 9/07/14

Theorem: The heap implementaEon realizes BuildHeap in Eme O(n). Proof: There are at most 2l nodes of depth l. A call of si down for each of these nodes takes Eme O(k l), k height of the tree. Get total runEme by summing up l=0, …, k 1

Algorithm and Data Structure Anal

8

Proof RunEme Build Total runEme: 





 

 











 xplanaEon:



 Algorithm and Data Structure Anal

9

Heapsort Want to have a SorEng algorithm based on heaps that runs in Eme O(n log n). Idea: Build the heap for n elements in Eme O(n). Pick in each step the maximum element (root) and delete it. (Time O(log n)) Iterate unEl heap is empty. In total n iteraEons implies total runEme O(n log n) Algorithm and Data Structure Anal

10

Heapsort Given , an in place sorEng algorithm is easily constructed: Maximum element is at A[1] Discard by swapping with element at A[n] Decrement heap_size[A] A[n] now contains correct value

Restore heap property at A[1] by calling Repeat, always swapping A[1] for A[heap_size(A)] Algorithm and Data Structure Anal 11 9/07/14

Heapsort

Algorithm and Data Structure Anal 12 9/07/14

Analyzing Heapsort The call to takes O(n) Eme ach of the n 1 calls to takes O(lg n) Eme Thus the total Eme taken by = O(n) + (n 1) O(lg n) = O(n) + O(n lg n) = O(n lg n)

Algorithm and Data Structure Anal 22 9/07/14

Priority Queues Heapsort is a nice algorithm, but in pracEce Quicksort (coming up) usually wins But the heap data structure is incredibly useful for implemenEng priority queues A data structure for maintaining a set S of elements, each with an associated value or key Supports the operaEons , , and What might a priority queue be useful for? Algorithm and Data Structure Anal 23 9/07/14

Priority Queue OperaEons Insert(S, x) inserts the element x into set S Maximum(S) returns the element of S with the maximum key ExtractMax(S) removes and returns the element of S with the maximum key How could we implement these opera2ons using a heap? Algorithm and Data Structure Anal 24 9/07/14

ImplemenEng Priority Queues ’

ImplemenEng Priority Queues

ImplemenEng Priority Queues...