Sorting Lower Bound (DETAIL)• Want: log(n!) ∈ Θ(n log n)• Claim: log(n!) ∈ O(n log n)n! ≤ nn⇒ log n! ≤ n log n• Claim: log(n!) ∈ Ω(n log n)n! ≥ (n/2)n/2⇒ log n! ≥ n/2 log(n/2) ⇒ 2 log n! ≥ n log (n/2) Observe: log (n/2) + 1 = log n 2 log (n/2) ≥ log n ∀n > 2 ⇒ 4 log n! ≥ n 2 log (n/2) ⇒ 4 log n! ≥ n log nDistribution Counting (8.2)• Array A contains n elements from {1,...,m}, m<<nfor j = 0 to m-1 do count[j] = 0 // initialize m countersfor i = 1 to n do // count incidences of each valuecount[A[i]] = count[A[i]] +1for j = 1 to m-1 do // change to running totals of countscount[j] = count[j-1] + count [j]for i = n down to 1 do // put each type into auxiliary array BB[count[A[i]]] = A[i]; count [a[i]] = count[a[i]] - 1for i =1 to n do A[i] = B[i] // copy back into original array• Complexity: O(n)Radix Sort (A Linear-Time Sort) (8.3)• Suppose all n elements in sorting instance have bounded size, e.g., in {0, ..., rd–1}• Radix Sort – Make sure list is sorted with respect to each digit position, starting with rightmost digit position– Use distribution counting to sort at each digit position– Total of nd digit comparisons to sort n d-digit numbers100 100 100 000001 010 000 001010 à 000 à 001 à 010111 001 101 100101 111 010 101000 101 111 111Dynamic Sets (III / Chapter 10)• Dynamic sets (data structures): – change a dictionary, e.g., add/remove words– reuse of structured information– fast updating for on-line algorithms• Elements:– key field is the element ID• dynamic set of key values– satellite information is not used in data organization • Operations– query: return information about the set– modify: change the setkeysatellitedatax→recordDynamic Set Operations• Search(S,k) – Given set S and key value k, return pointer x to an element of S such that key[x] = k, or NIL if no such element query• Insert(S,x)– Augment set S with element pointed to by x modify• Delete(S,x) – Given pointer x to an element in set S, remove x from S modify• Minimum(S) / Maximum(S)– Given totally ordered set S, return pointer to element of S with smallest / largest key queryDynamic Set Operations• Predecessor / Successor(S, x)– Given element x whose key is from a totally ordered set S, return a pointer to next smaller / larger element in S, or NIL if x is minimum / maximum element query• Union(S, S’)– Given two sets S, S’, return a new set S = S ∪ S’ modifyElementary Data Structures (10.1/11.1 )• Different data structures support/optimize different operations• Stack has top, LIFO policy– insert = push x: top(S) = top(S)+1); S[top(S)] = x O(1)– delete = pop O(1)• Queue has head, tail, FIFO policy– insert = enqueue: add element to the tail O(1)– delete = dequeue: remove element from the head O(1)15 6 2 91 2 3 4 5 6 7top[S] = 415 6 2 9 171 2 3 4 5 6 7After push(S,17) top[S] = 515 6 2 91 2 3 4 5 6 7tail = 6head = 215 6 2 9 81 2 3 4 5 6 7After enqueue(Q,8) tail = 7head = 2Note: head index is lower than tail index à opposite of Figure 10.2 in textbook.Priority Queue Abstract Data Structure (6.5)• Operations:– Insert(S,x): add element x– Minimum(S) / Maximum(S): return element with min/max key– DeleteMin(S) / DeleteMax(S): return min/max key, remove element• Applications– Simulation systems: key ≡ event time– OS scheduler: key ≡ job priority– Numerical methods key ≡ inherent error in operation– Dijkstra’s shortest-path alg, Prim’s minimum spanning tree alg• Q: How do we use a PQ to sort?• A: Insert elements one by one; perform DeleteMin n timesWhat Are Naïve PQ Implementations?• Unordered list– Insert O(1)– DeleteMin O(n)• Ordered list– Insert O(n)– DeleteMin O(1)• If Insert, DeleteMin each accomplished in O(log n) time ⇒ O(n log n) sorting algorithm!Heaps (6.1)• A heap is a binary tree of depth d such that– (1) all nodes not at depth d-1 or d are internal nodes à each level is filled before the next level is started– (2) at depth d-1 the internal nodes are to the left of the leaves and have degree 2, except perhaps for the rightmost, which has a left child à each level is filled left to right• A max heap (min heap) is a heap with node labels from an ordered set, such that the label at any internal node is ≥ (≤) the label of any of its childrenà All root-leaf paths are monotoneHeaps, and Sorting With Heaps• (Every node in a heap is the root of a heap!)• How do we store a heap?– Implicit data structure: // maxheap exampleArray index: 1 2 3 4 5 6 7 8 9 10Value: 20 11 5 5 3 2 3 4 1 2– A[i] is parent of A[2i] and A[2i+1]• How do we sort using a heap?– Insert: Put new value at A[n]; fix violation of heap condition (“re-heapify”)– DeleteM*: Remove root; replace by A[n]; re-heapify• If maxheap, DeleteMax (return largest element first)• If minheap, DeleteMin (return smallest element first)Heaps (6.1/7.1)• Pointers:– Parent parent of A[i] has index = i div 2– Left, Right (children) children of A[i] have indices 2i, 2i+1• Parent ≤ Child à this is a minheap example1261112813104952 36 78 9 10542 6 4 8 11 5 91 2 3 4 5 6 71081391210Heap Operations (6.2-5/7.2-5)241112813106973243128131069711241112813106973Insert(S,x): O(height) à O(log n)Extract-min(S): return head, replace head key with the last key, float down à O(log n) 26111281310495126118131049546118131012954611813105912“Float down”: If heap condition violated, swap with smaller childKeep swapping with parent until heap condition satisfiedHeapsort (6.4/7.4)• Build heap: n x O(log n) time– for i = 1..n do insert (A[1..i],A[i])• Extract elements in sorted order: n x O(log n) time– for i = n..2 do• Swap (A[1] ↔ A[i])• Heapsize = Heapsize-1• Float down A[1]46118131059712126118131059741261181310597412611813105974126118131059741261181310597412611813105974126118131059 74Actual Time To Build Heap = O(n) (6.3)• Heapify (i,j) makes range [i,j] satisfy heap property:Heapify (i,j) // minheap exampleif i not a leaf and child of i is > ilet k = larger child of iinterchange a[i], a[k]Heapify (k,j)• BuildHeap: for i=n to 1 do Heapify (i,n) • Observe: If vertices i+1, ..., n are roots of heaps, then afterHeapify(i,n) vertices