Lecture 8: Sorting I: Heaps Lecture Overview • Review: Insertion Sort and Merge Sort • Selection Sort • Heaps Readings CLRS 2.1, 2.2, 2.3, 6.1, 6.2, 6.3 and 6.4 Sorting Review Insertion Sort key θ(n2) algorithm 2 4 6 1 3 2 5 4 6 1 1 2 3 4 5 2 4 5 1 3 5 1 2 4 5 6 6 3 6 2 4 5 6 1 3 3 Figure 1: Insertion Sort Example Merge Sort Divide n-element array into two subarrays of n/2 elements each. Recursively sort sub-arrays using mergesort. Merge two sorted subarrays. 1 L θ(n) time 2 4 5 7 θ(n) auxiliary A space R 1 2 3 6 1 2 2 3 4 5 6 7 A[1: n/2] A[n/2+1: n] 2 4 5 7 1 2 3 6 want sorted A[1: n] w/o auxiliary space?? Figure 2: Merge Sort Example In-Place Sorting Numbers re-arranged in the array A with at most a constant number of them sorted outside the array at any time. Insertion Sort: stores key outside array Θ(n2 ) in-place Merge Sort: Need O(n) auxiliary space Θ(n lg n) during merging Question: Can we have Θ(n lg n) in-place sorting? Selection Sort 0. i=1 1. Find minimum value in list beginning with i 2. Swap it with the value in ith position 3. i = i + 1, stop if i = n Iterate steps 0-3 n times. Step 1 takes O(n) time. Can we improve to O(lg n)? 2 2 1 5 4 1 2 5 4 1 2 5 4 1 2 4 5 i=1 θ(n ) time in-place 2 Figure 3: Selection Sort Example Heaps (Not garbage collected storage) A heap is an array object that is viewed as a nearly complete binary tree. 1 16 4 8 2 6 9 5 7 8 9 4 1 2 3 4 5 6 7 8 9 10 3 2 14 16 14 10 8 7 9 7 3 1 Figure 4: Binary Heap Data Structure root A[i] Node with index i PARENT(i) = � 2i � LEFT(i) = 2i RIGHT(i) = 2i + 1 Note: NO POINTERS! 3 10 3 2 4 1 length[A]: number of elements in the array heap-size[A]: number of elements in the heap stored within array A heap-size[A]: ≤ length[A] Max-Heaps and Min-Heaps Max-Heap Property: For every node i other than the root A[PARENT(i)] ≥ A[i] Height of a binary heap O(lg n) MAX HEAPIFY: O(lg n) maintains max-heap property BUILD MAX HEAP: O(n) produces max-heap from unordered input array HEAP SORT: O(n lg n) Heap operations insert, extract max etc O(lg n). Max Heapify(A,i) l ← left(i) r ← right(i) if l ≤ heap-size(A) and A[l] > A[i] then largest ← l else largest ← i if r ≤ heap-size(A) and A[r] > largest then largest ← r if largest = � i then exchange A[i] and A[largest] MAX HEAPIFY(A, largest) This assumes that the trees rooted at left(i) and Right(i) are max-heaps. A[i] may be smaller than children violating max-heap property. Let the A[i] value “ﬂoat down” so subtree rooted at index i becomes a max-heap. 4 Example 1 16 2 4 8 7 3 10 1 9 8 2 6 9 5 7 14 MAX_HEAPIFY (A,2) heap_size[A] = 10 10 3 4 1 16 10 3 2 14 4 8 7 3 10 1 9 8 2 6 9 5 7 4 Exchange A[2] with A[4] Call MAX_HEAPIFY(A,4) because max_heap property is violated 1 16 10 3 2 14 4 8 2 6 9 5 7 8 9 4 Exchange A[4] with A[9] No more calls 1 7 3 10 Figure 5: MAX HEAPIFY Example 5

Lecture 8: Sorting I - Heaps

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock