Priority Queue ADTHeaps and HeapsortBinomial QueuesPriority Queues2Separate interface and implementation so as to•build layers of abstraction•reuse softwareEx: pushdown stack, FIFO queueinterface: description of data type, basic operationsclient: program using operations defined in interfaceimplementation: actual code implementing operationsClient can't know details of implementation•therefore has many implementations to choose fromImplementation can't know details of client needs•therefore many clients can use the same implementationAbstract data types (ADTs)3Performance matters!ADT allows use of better algorithm (without any change to client)Idealized scenario•design general-purpose ADT useful for many clients•develop efficient implementation of all ADT functionsEach ADT provides a new level of abstractionTotal cost depends on•ADT implementation (algorithm)•client usage patternMight need different implementations for different clientsADTs and algorithmsclientquicksortstacklinked listADTclientsalgorithmsEx:4Records with keys (priorities)basic operations•insert•remove largest•create•test if empty•destroy•copyExample clients•simulation•numerical computation•data compression•graph searchingBasic Priority Queue ADTnot needed for one-time usebut critical in large systemsstay tunedvoid PQinit();void PQinsert(Item);Item PQdelmax/min(); int PQempty();PQ.hPQ interface in Cgeneric operationscommon to many ADTscan substitute smallest for clarity but not both in same client5EEXEXAEAEAMEAEA PEAPLEALEALEEAEAEAPQ exampleinsert Einsert Xinsert Ainsert Minsert Pinsert Linsert Eremove largestXremove largestremove largestremove largestremove largestremove largestremove largestMPLEEA6PQ client exampleProblem: Find the largest M of a stream of N elementsExample application: Fraud detection (isolate $$ transactions)Constraint: May not have memory to store N elementsSolution: Use a priority queuetime spaceelementary PQNM Mheap/BQN lgM MselectNNPQinit();for (k = 0; k < M; k++) PQinsert(nextItem());for (k = M; k < N; k++) { PQinsert(nextItem()); t = PQdelmin(); }for (k = 0; k < M; k++) a[k] = PQdelmin();add nextdiscard smallestM largestleft on PQEx: top 10,000 in a stream of 1 billionnot possible without good algorithm (also can adapt select)7Unordered-array PQ implementationinsertremove largestcreatefindmaxtest if emptystatic Item *pq;static int N;PQinsert(Item v) { pq[N++] = v; }Item PQdelmax() { int j, max = 0; for (j = 1; j < N; j++) if (less(pq[max], pq[j])) max = j; exch(pq[max], pq[N]); return pq[--N]; }void PQinit(int maxN) { pq = malloc((maxN+1)*sizeof(Item)); N = 0; }int PQempty() { return N == 0; }some otherimplementationsneed sentinel8PQ implementations cost summaryinsertremovemaxremovefindmaxchangekeyjoinordered arrayN1N1NNordered listN111NNunordered array1N1N1Nunordered list1N1N11heaplg Nlg Nlg N1lg N Nbinomial queuelg Nlg Nlg Nlg Nlg N lg Nbest in theory1lg Nlg N111Worst-case asymptotic costs for a PQ with N itemsCan we implement both operations efficiently?9Heap: Array representation of a heap-ordered complete binary treeBinary tree•null or•node with links to left and right treesHeap-ordered binary tree•keys in nodes•no smaller than children’s keysArray representation•take nodes in level order•no explicit linksXTOGSMNAERAI1234567891011 12Heap123456789101112X T O G S M N A E R A Icomplete tree:balanced exceptfor bottom level10Largest key is at rootCan use array indices to move through tree•parent of node at k is at k/2•children of node at k are at 2k and 2k+1Length of path in N-node heap is at most ~lg Nn levels when 2n≤ N < 2n+1n ≤ lg N < n+1~lg N levels2n-1 nodesHeap propertiesXTOGSMNAERAI1234567891011 121234567891011 12X T O G SMN A E R A I2n nodeslevel123...n-1n11XTOGSMNAERAI PSuppose that a node at the bottom is larger than its parentInvariant: Heap condition violated only at that nodeTo eliminate the violation•exchange with parent•maintains invariant (why?)•moves up the tree•continue until node not larger than parentPromotion (bubbling up) in a heap1234567891011 12 13X T O G S M N A E R A I PX T P G S O N A E R A I Mswim(Item a[], int k) { while (k > 1 && less(a[k/2], a[k])) { exch(a[k], a[k/2]); k = k/2; } }Peter principle: node rises to level of incompetenceparent of node at k is at k/2XTOGSPNAERAIMXTPGSONAERAIM12sink(Item a[], int k, int N) { int j; while (2*k <= N) { j = 2*k; if (j < N && less(a[j], a[j+1])) j++; if (!less(a[k], a[j])) break; exch(a[k], a[j]); k = j; } }Suppose that a node at the top is smaller than a childInvariant: Heap condition violated only at that nodeTo eliminate the violation•exchange with larger child•maintains invariant (why?)•moves down the tree•continue until node not smaller than childrenDemotion (sifting down) in a heap1234567891011 12 13O T X G S P N A E R A I MX T P G S O N A E R A I MPower struggle: better subordinate promotedOTXGSPNAERAIMchildren of node at k are at 2k and 2k+1XTOGSPNAERAIMXTPGSONAERAIM13XTOGSMNAERAI Psame as elementaryarray-basedHeap-based PQ implementationinsertremove largestinsert add node at end, then promoteremove largest exchange root with node at end, then sift downX T O G S M N A E R A I PX T P G S O N A E R A I MT S P G R O N A E M A IXTSPGRONAEMAIXstatic Item *pq;static int N;void PQinit(int maxN);int PQempty();PQinsert(Item v) { pq[N++] = v; swim(pq, N); }Item PQdelmax() { exch(pq[1], pq[N]); sink(pq, 1, N-1); return pq[N--]; }XTPGSONAERAIM14PQ implementations cost summaryinsertremovemaxremovefindmaxchangekeyjoinordered arrayN1N1NNordered listN111NNunordered array1N1N1Nunordered list1N1N11heaplg Nlg Nlg N1lg N Nbinomial queuelg Nlg Nlg Nlg Nlg N lg Nbest in theory1lg Nlg N111Worst-case asymptotic costs for a PQ with N items15#define pq(A) a[L-1+A]void heapsort(Item a[], int L, int R) { int k, N = r-l+1; for (k = 2; k <= N; k++) swim(&pq(0), k); while (N > 1) { exch(pq(1), pq(N)); sink(&pq(0), 1, --N); } }Digression: HeapsortbuildheapFirst pass: build heap add item to heap at each iteration, then sift up (or can use faster bottom-up method; see book)Second pass: sortremove maximum at each iterationexchange root with node at end, then sift downremovemaximum;sift downEXAMPLEEXAMPLEX EAMP L EX E AM P L EX M A EPLEX P A E ML EX P L E M AEX P L E M A EP M L E E AXM E L A EPXL E E AM P XE A ELMPXE
View Full Document
Unlocking...