《第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables.ppt》由会员分享，可在线阅读，更多相关《第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Priority Queue ADTwA priority queue stores a collection of itemswAn item is a pair(key,element)wMain methods of the Priority Queue ADTninsertItem(k,o)inserts a
2、n item with key k and element onremoveMin()removes the item with smallest key and returns its elementwAdditional methodsnminKey()returns,but does not remove,the smallest key of an itemnminElement()returns,but does not remove,the element of an item with smallest keynsize(),isEmpty()wApplications:nSta
3、ndby flyersnAuctionsnStock market11/16/20222Priority QueuesTotal Order RelationwKeys in a priority queue can be arbitrary objects on which an order is definedwTwo distinct items in a priority queue can have the same keywMathematical concept of total order relation nReflexive property:x xnAntisymmetr
4、ic property:x y y x x=ynTransitive property:x y y z x z11/16/20223Priority QueuesComparator ADTwA comparator encapsulates the action of comparing two objects according to a given total order relationwA generic priority queue uses an auxiliary comparatorwThe comparator is external to the keys being c
5、omparedwWhen the priority queue needs to compare two keys,it uses its comparatorwMethods of the Comparator ADT,all with Boolean return typenisLessThan(x,y)nisLessThanOrEqualTo(x,y)nisEqualTo(x,y)nisGreaterThan(x,y)nisGreaterThanOrEqualTo(x,y)nisComparable(x)11/16/20224Priority QueuesSorting with a P
6、riority QueueWe can use a priority queue to sort a set of comparable elements1.Insert the elements one by one with a series of insertItem(e,e)operations2.Remove the elements in sorted order with a series of removeMin()operationsThe running time of this sorting method depends on the priority queue im
7、plementationAlgorithm PQ-Sort(S,C)Input sequence S,comparator C for the elements of SOutput sequence S sorted in increasing order according to CP priority queue with comparator Cwhile S.isEmpty()e S.remove(S.first()P.insertItem(e,e)while P.isEmpty()e P.removeMin()S.insertLast(e)11/16/20225Priority Q
8、ueuesSequence-based Priority QueuewImplementation with an unsorted sequencenStore the items of the priority queue in a list-based sequence,in arbitrary orderwPerformance:ninsertItem takes O(1)time since we can insert the item at the beginning or end of the sequencenremoveMin,minKey and minElement ta
9、ke O(n)time since we have to traverse the entire sequence to find the smallest key wImplementation with a sorted sequencenStore the items of the priority queue in a sequence,sorted by keywPerformance:ninsertItem takes O(n)time since we have to find the place where to insert the itemnremoveMin,minKey
10、 and minElement take O(1)time since the smallest key is at the beginning of the sequence11/16/20226Priority QueuesSelection-SortSelection-sort is the variation of PQ-sort where the priority queue is implemented with an unsorted sequenceRunning time of Selection-sort:1.Inserting the elements into the
11、 priority queue with n insertItem operations takes O(n)time2.Removing the elements in sorted order from the priority queue with n removeMin operations takes time proportional to 1+2+nSelection-sort runs in O(n2)time 11/16/20227Priority QueuesInsertion-SortInsertion-sort is the variation of PQ-sort w
12、here the priority queue is implemented with a sorted sequenceRunning time of Insertion-sort:1.Inserting the elements into the priority queue with n insertItem operations takes time proportional to 1+2+n2.Removing the elements in sorted order from the priority queue with a series of n removeMin opera
13、tions takes O(n)timeInsertion-sort runs in O(n2)time 11/16/20228Priority QueuesIn-place Insertion-sortwInstead of using an external data structure,we can implement selection-sort and insertion-sort in-placewA portion of the input sequence itself serves as the priority queuewFor in-place insertion-so
14、rtnWe keep sorted the initial portion of the sequencenWe can use swapElements instead of modifying the sequence5423154231452312453123451123451234511/16/20229Priority QueuesWhat is a heap(2.4.3)A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:nHeap-Or
15、der:for every internal node v other than the root,key(v)key(parent(v)nComplete Binary Tree:let h be the height of the heapwfor i=0,h-1,there are 2i nodes of depth iwat depth h-1,the internal nodes are to the left of the external nodes26579The last node of a heap is the rightmost internal node of dep
16、th h-1last node11/16/202210Priority QueuesHeight of a Heap(2.4.3)Theorem:A heap storing n keys has height O(log n)Proof:(we apply the complete binary tree property)nLet h be the height of a heap storing n keysnSince there are 2i keys at depth i=0,h-2 and at least one key at depth h-1,we have n 1+2+4
17、+2h-2 +1 nThus,n 2h-1,i.e.,h log n+1122h-21keys01h-2h-1depth11/16/202211Priority QueuesHeaps and Priority QueuesWe can use a heap to implement a priority queueWe store a(key,element)item at each internal nodeWe keep track of the position of the last nodeFor simplicity,we show only the keys in the pi
18、ctures(2,Sue)(6,Mark)(5,Pat)(9,Jeff)(7,Anna)11/16/202212Priority QueuesInsertion into a Heap(2.4.3)wMethod insertItem of the priority queue ADT corresponds to the insertion of a key k to the heapwThe insertion algorithm consists of three stepsnFind the insertion node z(the new last node)nStore k at
19、z and expand z into an internal nodenRestore the heap-order property(discussed next)26579insertion node265791zz11/16/202213Priority QueuesUpheapAfter the insertion of a new key k,the heap-order property may be violatedAlgorithm upheap restores the heap-order property by swapping k along an upward pa
20、th from the insertion nodeUpheap terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k Since a heap has height O(log n),upheap runs in O(log n)time215796z125796z11/16/202214Priority QueuesRemoval from a Heap(2.4.3)Method removeMin of the priority queu
21、e ADT corresponds to the removal of the root key from the heapThe removal algorithm consists of three stepsnReplace the root key with the key of the last node wnCompress w and its children into a leafnRestore the heap-order property(discussed next)26579last nodew7659w11/16/202215Priority QueuesDownh
22、eapAfter replacing the root key with the key k of the last node,the heap-order property may be violatedAlgorithm downheap restores the heap-order property by swapping key k along a downward path from the rootUpheap terminates when key k reaches a leaf or a node whose children have keys greater than
23、or equal to k Since a heap has height O(log n),downheap runs in O(log n)time7659w5679w11/16/202216Priority QueuesUpdating the Last NodeThe insertion node can be found by traversing a path of O(log n)nodesnWhile the current node is a right child,go to the parent nodenIf the current node is a left chi
24、ld,go to the right childnWhile the current node is internal,go to the left childSimilar algorithm for updating the last node after a removal11/16/202217Priority QueuesHeap-Sort(2.4.4)wConsider a priority queue with n items implemented by means of a heapnthe space used is O(n)nmethods insertItem and
25、removeMin take O(log n)timenmethods size,isEmpty,minKey,and minElement take time O(1)timewUsing a heap-based priority queue,we can sort a sequence of n elements in O(n log n)timewThe resulting algorithm is called heap-sortwHeap-sort is much faster than quadratic sorting algorithms,such as insertion-
26、sort and selection-sort11/16/202218Priority QueuesVector-based Heap Implementation(2.4.3)We can represent a heap with n keys by means of a vector of length n+1For the node at rank inthe left child is at rank 2inthe right child is at rank 2i+1Links between nodes are not explicitly storedThe leaves ar
27、e not representedThe cell at rank 0 is not usedOperation insertItem corresponds to inserting at rank n+1Operation removeMin corresponds to removing at rank nYields in-place heap-sort265792569712345011/16/202219Priority QueuesMerging Two HeapsWe are given two two heaps and a key kWe create a new heap
28、 with the root node storing k and with the two heaps as subtreesWe perform downheap to restore the heap-order property 7358264358264235846711/16/202220Priority QueuesWe can construct a heap storing n given keys in using a bottom-up construction with log n phasesIn phase i,pairs of heaps with 2i-1 ke
29、ys are merged into heaps with 2i+1-1 keysBottom-up Heap Construction2i-12i-12i+1-111/16/202221Priority QueuesExample15161249620232515165124119627202311/16/202222Priority QueuesExample(contd.)251516512411962720231525164125691123202711/16/202223Priority QueuesExample(contd.)715251641258691123202741525
30、1651276891123202711/16/202224Priority QueuesExample(end)41525165127106891123202751525167121046891123202711/16/202225Priority QueuesAnalysisWe visualize the worst-case time of a downheap with a proxy path that goes first right and then repeatedly goes left until the bottom of the heap(this path may d
31、iffer from the actual downheap path)Since each node is traversed by at most two proxy paths,the total number of nodes of the proxy paths is O(n)Thus,bottom-up heap construction runs in O(n)time Bottom-up heap construction is faster than n successive insertions and speeds up the first phase of heap-s
32、ort11/16/202226Priority QueuesDictionaries and Hash Tables01234451-229-0004981-101-0002025-612-000111/16/202227Priority QueuesDictionary ADT(2.5.1)wThe dictionary ADT models a searchable collection of key-element itemswThe main operations of a dictionary are searching,inserting,and deleting itemswMu
33、ltiple items with the same key are allowedwApplications:naddress bookncredit card authorizationnmapping host names(e.g.,)to internet addresses(e.g.,128.148.34.101)wDictionary ADT methods:nfindElement(k):if the dictionary has an item with key k,returns its element,else,returns the special element NO_
34、SUCH_KEY ninsertItem(k,o):inserts item(k,o)into the dictionarynremoveElement(k):if the dictionary has an item with key k,removes it from the dictionary and returns its element,else returns the special element NO_SUCH_KEY nsize(),isEmpty()nkeys(),elements()11/16/202228Priority QueuesLog File(2.5.1)wA
35、 log file is a dictionary implemented by means of an unsorted sequencenWe store the items of the dictionary in a sequence(based on a doubly-linked lists or a circular array),in arbitrary orderwPerformance:ninsertItem takes O(1)time since we can insert the new item at the beginning or at the end of t
36、he sequencenfindElement and removeElement take O(n)time since in the worst case(the item is not found)we traverse the entire sequence to look for an item with the given keywThe log file is effective only for dictionaries of small size or for dictionaries on which insertions are the most common opera
37、tions,while searches and removals are rarely performed(e.g.,historical record of logins to a workstation)11/16/202229Priority QueuesHash Functions and Hash Tables(2.5.2)wA hash function h maps keys of a given type to integers in a fixed interval 0,N -1wExample:h(x)=x mod Nis a hash function for inte
38、ger keyswThe integer h(x)is called the hash value of key xwA hash table for a given key type consists ofnHash function hnArray(called table)of size NwWhen implementing a dictionary with a hash table,the goal is to store item(k,o)at index i=h(k)11/16/202230Priority QueuesExampleWe design a hash table
39、 for a dictionary storing items(SSN,Name),where SSN(social security number)is a nine-digit positive integerOur hash table uses an array of size N =10,000 and the hash functionh(x)=last four digits of x01234999799989999451-229-0004981-101-0002200-751-9998025-612-000111/16/202231Priority QueuesHash Fu
40、nctions(2.5.3)wA hash function is usually specified as the composition of two functions:Hash code map:h1:keys integersCompression map:h2:integers 0,N -1The hash code map is applied first,and the compression map is applied next on the result,i.e.,h(x)=h2(h1(x)The goal of the hash function is to “disp
41、erse”the keys in an apparently random way11/16/202232Priority QueuesHash Code Maps(2.5.3)wMemory address:nWe reinterpret the memory address of the key object as an integer(default hash code of all Java objects)nGood in general,except for numeric and string keyswInteger cast:nWe reinterpret the bits
42、of the key as an integernSuitable for keys of length less than or equal to the number of bits of the integer type(e.g.,byte,short,int and float in Java)wComponent sum:nWe partition the bits of the key into components of fixed length(e.g.,16 or 32 bits)and we sum the components(ignoring overflows)nSu
43、itable for numeric keys of fixed length greater than or equal to the number of bits of the integer type(e.g.,long and double in Java)11/16/202233Priority QueuesHash Code Maps(cont.)Polynomial accumulation:nWe partition the bits of the key into a sequence of components of fixed length(e.g.,8,16 or 32
44、 bits)a0 a1 an-1nWe evaluate the polynomialp(z)=a0+a1 z +a2 z2+an-1zn-1at a fixed value z,ignoring overflowsnEspecially suitable for strings(e.g.,the choice z=33 gives at most 6 collisions on a set of 50,000 English words)Polynomial p(z)can be evaluated in O(n)time using Horners rule:nThe following
45、polynomials are successively computed,each from the previous one in O(1)timep0(z)=an-1pi(z)=an-i-1+zpi-1(z)(i=1,2,n-1)We have p(z)=pn-1(z)11/16/202234Priority QueuesCompression Maps(2.5.4)wDivision:nh2(y)=y mod NnThe size N of the hash table is usually chosen to be a prime nThe reason has to do with
46、 number theory and is beyond the scope of this coursewMultiply,Add and Divide(MAD):nh2(y)=(ay+b)mod Nna and b are nonnegative integers such that a mod N 0nOtherwise,every integer would map to the same value b 11/16/202235Priority QueuesCollision Handling(2.5.5)wCollisions occur when different elemen
47、ts are mapped to the same cellwChaining:let each cell in the table point to a linked list of elements that map therewChaining is simple,but requires additional memory outside the table01234451-229-0004981-101-0004025-612-000111/16/202236Priority QueuesLinear Probing(2.5.5)Open addressing:the collidi
48、ng item is placed in a different cell of the tableLinear probing handles collisions by placing the colliding item in the next(circularly)available table cellEach table cell inspected is referred to as a“probe”Colliding items lump together,causing future collisions to cause a longer sequence of probe
49、swExample:nh(x)=x mod 13nInsert keys 18,41,22,44,59,32,31,73,in this order 0123456789 10 11 12 41 18 44 59 32 22 31 73 0123456789 10 11 1211/16/202237Priority QueuesSearch with Linear ProbingwConsider a hash table A that uses linear probingwfindElement(k)nWe start at cell h(k)nWe probe consecutive l
50、ocations until one of the following occurswAn item with key k is found,orwAn empty cell is found,orwN cells have been unsuccessfully probed Algorithm findElement(k)i h(k)p 0repeatc Aiif c=return NO_SUCH_KEY else if c.key()=kreturn c.element()elsei (i+1)mod Np p+1until p=Nreturn NO_SUCH_KEY11/16/2022