第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables.ppt
《第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables.ppt》由会员分享,可在线阅读,更多相关《第02章基本数据结构PriorityQueuesHeapsDictionariesHashTables.ppt(45页珍藏版)》请在三一办公上搜索。
1、11/18/2023 10:24 AM,Priority Queues,1,Priority Queues,11/18/2023 10:24 AM,Priority Queues,2,Priority Queue ADT,A priority queue stores a collection of itemsAn item is a pair(key,element)Main methods of the Priority Queue ADTinsertItem(k,o)inserts an item with key k and element oremoveMin()removes th
2、e item with smallest key and returns its element,Additional methodsminKey()returns,but does not remove,the smallest key of an itemminElement()returns,but does not remove,the element of an item with smallest keysize(),isEmpty()Applications:Standby flyersAuctionsStock market,11/18/2023 10:24 AM,Priori
3、ty Queues,3,Total Order Relation,Keys in a priority queue can be arbitrary objects on which an order is definedTwo distinct items in a priority queue can have the same key,Mathematical concept of total order relation Reflexive property:x xAntisymmetric property:x y y x x=yTransitive property:x y y z
4、 x z,11/18/2023 10:24 AM,Priority Queues,4,Comparator ADT,A comparator encapsulates the action of comparing two objects according to a given total order relationA generic priority queue uses an auxiliary comparatorThe comparator is external to the keys being comparedWhen the priority queue needs to
5、compare two keys,it uses its comparator,Methods of the Comparator ADT,all with Boolean return typeisLessThan(x,y)isLessThanOrEqualTo(x,y)isEqualTo(x,y)isGreaterThan(x,y)isGreaterThanOrEqualTo(x,y)isComparable(x),11/18/2023 10:24 AM,Priority Queues,5,Sorting with a Priority Queue,We can use a priorit
6、y queue to sort a set of comparable elementsInsert the elements one by one with a series of insertItem(e,e)operationsRemove the elements in sorted order with a series of removeMin()operationsThe running time of this sorting method depends on the priority queue implementation,Algorithm PQ-Sort(S,C)In
7、put 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/18/2023 10:24 AM,Priority Queues,6,Sequence-based Pri
8、ority Queue,Implementation with an unsorted sequenceStore the items of the priority queue in a list-based sequence,in arbitrary orderPerformance:insertItem takes O(1)time since we can insert the item at the beginning or end of the sequenceremoveMin,minKey and minElement take O(n)time since we have t
9、o traverse the entire sequence to find the smallest key,Implementation with a sorted sequenceStore the items of the priority queue in a sequence,sorted by keyPerformance:insertItem takes O(n)time since we have to find the place where to insert the itemremoveMin,minKey and minElement take O(1)time si
10、nce the smallest key is at the beginning of the sequence,11/18/2023 10:24 AM,Priority Queues,7,Selection-Sort,Selection-sort is the variation of PQ-sort where the priority queue is implemented with an unsorted sequenceRunning time of Selection-sort:Inserting the elements into the priority queue with
11、 n insertItem operations takes O(n)timeRemoving 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/18/2023 10:24 AM,Priority Queues,8,Insertion-Sort,Insertion-sort is the variation of PQ-sort where the
12、priority queue is implemented with a sorted sequenceRunning time of Insertion-sort:Inserting the elements into the priority queue with n insertItem operations takes time proportional to 1+2+nRemoving the elements in sorted order from the priority queue with a series of n removeMin operations takes O
13、(n)timeInsertion-sort runs in O(n2)time,11/18/2023 10:24 AM,Priority Queues,9,In-place Insertion-sort,Instead of using an external data structure,we can implement selection-sort and insertion-sort in-placeA portion of the input sequence itself serves as the priority queueFor in-place insertion-sortW
14、e keep sorted the initial portion of the sequenceWe can use swapElements instead of modifying the sequence,11/18/2023 10:24 AM,Priority Queues,10,What is a heap(2.4.3),A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:Heap-Order:for every internal nod
15、e v other than the root,key(v)key(parent(v)Complete Binary Tree:let h be the height of the heapfor i=0,h-1,there are 2i nodes of depth iat depth h-1,the internal nodes are to the left of the external nodes,2,6,5,7,9,The last node of a heap is the rightmost internal node of depth h-1,last node,11/18/
16、2023 10:24 AM,Priority Queues,11,Height 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)Let h be the height of a heap storing n keysSince 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+2h-2+1 Th
17、us,n 2h-1,i.e.,h log n+1,1,2,2h-2,1,keys,0,1,h-2,h-1,depth,11/18/2023 10:24 AM,Priority Queues,12,Heaps and Priority Queues,We 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 ke
18、ys in the pictures,(2,Sue),(6,Mark),(5,Pat),(9,Jeff),(7,Anna),11/18/2023 10:24 AM,Priority Queues,13,Insertion into a Heap(2.4.3),Method insertItem of the priority queue ADT corresponds to the insertion of a key k to the heapThe insertion algorithm consists of three stepsFind the insertion node z(th
19、e new last node)Store k at z and expand z into an internal nodeRestore the heap-order property(discussed next),insertion node,2,6,5,7,9,1,z,z,11/18/2023 10:24 AM,Priority Queues,14,Upheap,After the insertion of a new key k,the heap-order property may be violatedAlgorithm upheap restores the heap-ord
20、er property by swapping k along an upward path 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)time,2,1,5,7,9,6,z,1,2,5,7,9,6,z,11/18/2023 10:24 AM,Priority Qu
21、eues,15,Removal from a Heap(2.4.3),Method removeMin of the priority queue ADT corresponds to the removal of the root key from the heapThe removal algorithm consists of three stepsReplace the root key with the key of the last node wCompress w and its children into a leafRestore the heap-order propert
22、y(discussed next),last node,w,7,6,5,9,w,11/18/2023 10:24 AM,Priority Queues,16,Downheap,After 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
23、terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k Since a heap has height O(log n),downheap runs in O(log n)time,7,6,5,9,w,11/18/2023 10:24 AM,Priority Queues,17,Updating the Last Node,The insertion node can be found by traversing a path of O(log n)no
24、desWhile the current node is a right child,go to the parent nodeIf the current node is a left child,go to the right childWhile the current node is internal,go to the left childSimilar algorithm for updating the last node after a removal,11/18/2023 10:24 AM,Priority Queues,18,Heap-Sort(2.4.4),Conside
25、r a priority queue with n items implemented by means of a heapthe space used is O(n)methods insertItem and removeMin take O(log n)timemethods size,isEmpty,minKey,and minElement take time O(1)time,Using a heap-based priority queue,we can sort a sequence of n elements in O(n log n)timeThe resulting al
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 02 基本 数据结构 PriorityQueuesHeapsDictionariesHashTables
链接地址:https://www.31ppt.com/p-6614718.html