DOC PREVIEW
UD CISC 320 - HeapSort

This preview shows page 1 out of 4 pages.

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

Unformatted text preview:

1CISC320, F05, Lec5, Liao 1CISC 320 Introduction to AlgorithmsFall 2005Lecture 5HeapSortCISC320, F05, Lec5, Liao2An idea to speedup Insertion Sort is, for a to-be-inserted key, use Binary search to find the proper position in the sorted segment. When i-th element is to be inserted, the sorted segment has size (i-1), and binary search takes O(lg(i-1)) = O(lg(i) to find the right position. Therefore the total cost isΣi=1 to nO(lg(i)) = O(n lg n). But, how to actually insert an element into an array? Need to move other elements to their right, one by one, to fill the vacancy left by the to-be-inserted key. And it takes same number of shifting as does the original insertion sort. How about to store the sorted segment in a linked list, so inserting a new element will be easy? But, binary search does not work fora linked list. How about to use instead a binary search tree? Yes. But an ordinary BST has O(n) worst case time.  Then a balanced BST, such as Red-black tree, will do it: in O(n lgn) time. This way, while we achieved lower bound in time, the algorithm is no longer “in-place”.Is there a data structure that help achieve both?CISC320, F05, Lec5, Liao3Heapsort Heap: a binary tree T that satisfies1. T is complete through depth h-12. All paths to a leaf of depth h are to the left of all paths to a leaf of depth h-1, i.e., leaves at level h are filled from left to right.3. Key at any node is greater than or equal to the keys at each of its children (for maximizing heap). This is called heap property or partial order tree property.CISC320, F05, Lec5, Liao4161410 8 7 9 3 2 4 11 2 3 4 5 6 7 8 9 10└n/2┘ +1leavesInternal nodes161482109 317412345678109Parent(i) = └i/2┘Left(i) = 2iRight(i) = 2i + 1CISC320, F05, Lec5, Liao5Maintain a Max-HeapLeft and right subtrees of i are already Max-HeapsMake subtree rooted at i a Max-HeapMax-Heapify(A, i) 1 l ← left(i); // l = 2i2 r ← right(i); // r = 2i+13 if ( l ≤ n and A[l] > A[i]) 4 then largest ← l;5 else largest ← i;6 if (r ≤ n and A[r] > A[largest])7 then largest ← r;8 if (largest ≠ i)9 then exchange A[i] ↔ A[largest];10 Max-Heapify(A, largest);Analysis:time is proportional to height of i∈O(lgn)CISC320, F05, Lec5, Liao6MAX-Heapify(A, 2)161442109 317812345678109161482109 317412345678109164142109 317812345678109a. Exchange A[2] with A[4] and recursively call heapify(A,4)b. Exchange A[4] with A[9] and recursively call heapify(A, 9)c. Node 9 has no children, so it is done.acb2CISC320, F05, Lec5, Liao7 Construct a Heap Convert an array A[1..n] into a Max-Heap Elements from n/2 +1 to n correspond to leaves, and themselves are 1-element heaps already.Build-Max-Heap(A) 1. For (i= floor(n/2); i > 1; i--)2. Max-Heapify(A, i); CISC320, F05, Lec5, Liao8c4121439 107168123456781094121439 107168123456781094121439 10716812345678109i4121439 107168123456781094121439 10716812345678109i4114239 107168123456781094114239 1071681234567810941142109 371681234567810941142109 3716812345678109iii4 1 3 2 16 9 1014 8 71 2 3 4 5 6 7 8 9 10AabdCISC320, F05, Lec5, Liao9416142109 317812345678109i161482109 317412345678109efCISC320, F05, Lec5, Liao10 Analysis of Build-Max-Heapn calls to heapify = n O(lg n) = O(n lg n) A tighter analysisT(n) = T(n-r-1) + T(r) + 2 lg(n)= 2T((n-1)/2) + 2 lg(n) // complete binary tree∈Θ(n) // master theorem heapifyright subtreeleft subtreeCISC320, F05, Lec5, Liao11HeapsortHeapsort(A)int heapsize = n;1. Build-Max-Heap(A); // O(n)2. for(i = heapsize; i > 2; i--) // n3. do exchange A[1] ↔ A[i]; // O(1)4. heapsize = heapsize – 1; // O(1)5. Max-Heapify(A, 1); // O(lg n)Time analysis:T(n) = O(n) + O(n lg n) = O(n lg n)isortedheap1nLargest key in the heapCISC320, F05, Lec5, Liao12 A more exact analysisT(n) = Θ(n) + 2 ∑i=1 to n-1└lg i┘≤Θ(n) + 2 ∫1n(lg e) ln x dx= Θ(n) + 2 (lg e) (n ln n – n)= Θ(n) + 2(n lg(n) – 1.443 n)= 2 n lg(n) + O(n)3CISC320, F05, Lec5, Liao13 Heap used as priority queue Max-Heap-Insert(S,x) inserts element x into the set S (time: ) Heap-Maximum(S) returns the element of S with the largest key (time: ) Heap-Extract-Max(S) removes and returns the element of S with the largest key (time: ) A heap can support any priority-queue operations on a set of size n in _ time.CISC320, F05, Lec5, Liao14Heap-extract-max(A)1. If heap-size(A) < 1 2. then error “heap underflow”3. max = A[1];4. A[1] = A[heap-size(A)]5. Heap-size(A) = heap-size(A) -16. Max-Heapify(A, 1)7. Return max;Note: Heap-extract-max takes only O(lg n) timeCISC320, F05, Lec5, Liao15Max-Heap-Insert(A, key)1. heap-size(A) = heap-size(A) + 12. i = heap-size(A)3. while (i > 1 and A[parent(i)] < key)4. exchange A[i] ↔ A[parent(i)]5. i = parent(i) Note: this is bubble-up heap, only requires one comparison at each level to float a big key to its right position (in contrast to heapify which requires two comparisons to filter down a small key)CISC320, F05, Lec5, Liao16Max-Heap-Insert(A, 15)161482109 317412345678109161482109 3174123456781091682109 31144123456781097161582109 31144123456781097CISC320, F05, Lec5, Liao17Comparison of sorting algorithmsAlgorithm Worst-case Average Space usageInsertionsort n2/2 Θ(n2) in placeQuicksort n2/2 Θ(n log n) extra space log nMergesort n lg n Θ(n log n) extra space nHeapsort 2n lg n Θ(n log n) in placeAccl. Heapsort n lg n Θ(n log n) in placeCISC320, F05, Lec5, Liao18Lower bounds: worst-case Decision tree approachnodes ↔ comparisons of keysleaves ↔ possible permutation of n keys (=n!)Height ↔ max # of comparisons≥ lg (# of leaves) = lg(n!)≥ (n/2)lg(n/2)∈Θ(n log n)i:jxi<xjxi>xjxixjxjxi4CISC320, F05, Lec5, Liao19Lower boundsAverage-Cas e Tav(n) = (sum of lengths of all paths from the root to a leaf) / (L, # of leaves) Balanced decision tree => lower Tav(n) A complete tree is most balanced: [L lg(L)] /L Therefore, Tav(n) ≥ lg(L) = lg(n!) ∈Θ(n log


View Full Document

UD CISC 320 - HeapSort

Download HeapSort
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 HeapSort 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 HeapSort 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?