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 n Distribution Counting 8 2 Array A contains n elements from 1 m m n for j 0 to m 1 do count j 0 initialize m counters for i 1 to n do count incidences of each value count A i count A i 1 for j 1 to m 1 do change to running totals of counts count j count j 1 count j for i n down to 1 do put each type into auxiliary array B B count A i A i count a i count a i 1 for 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 numbers 100 001 010 111 101 000 100 010 000 001 111 101 100 000 001 101 010 111 000 001 010 100 101 111 Dynamic Sets III Chapter 10 Dynamic sets data structures change a dictionary e g add remove words reuse of structured information record fast updating for on line algorithms x key Elements key field is the element ID satellite data dynamic set of key values satellite information is not used in data organization Operations query return information about the set modify change the set Dynamic 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 query Dynamic 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 modify Elementary 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 1 2 3 4 5 6 7 15 6 2 9 1 2 3 4 5 6 7 15 6 2 9 17 top S 4 After push S 17 top S 5 Queue has head tail FIFO policy insert enqueue add element to the tail O 1 delete dequeue remove element from the head O 1 1 2 3 4 5 6 7 15 6 2 9 head 2 1 2 3 4 5 6 7 15 6 2 9 8 tail 6 head 2 After enqueue Q 8 tail 7 Note 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 times What 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 monotone Heaps 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 example Array index 1 2 3 4 5 6 7 8 9 10 Value 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 2 1 1 6 4 2 3 11 5 9 4 5 6 7 13 12 8 9 10 3 4 5 6 7 8 9 10 2 6 4 8 11 5 9 10 13 12 8 10 2 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 example Heap Operations 6 2 5 7 2 5 2 2 4 8 10 6 11 13 7 4 9 3 12 2 6 8 3 7 10 13 12 11 9 8 10 12 6 4 8 10 13 11 12 5 6 9 8 10 13 5 13 12 6 9 9 11 4 4 11 7 4 Keep swapping with parent until heap condition satisfied Insert S x O height O log n 2 6 3 8 10 13 4 12 11 5 6 9 8 5 11 12 9 10 13 Extract min S return head replace head key Float down If heap violated with the last key float down O log n condition swap with smaller child Heapsort 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 …