【精品数据结构】PriorityQueues.pptVIP

Chapter 9 Priority Queues 9.1 Introduction A priority queue is a collection of zero or more elements. Each element has a priority or value. Operations: 1)find an element 2)insert a new element 3)delete an element 9.1 Introduction In a min priority queue the find operation finds the element with minimum priority, while the delete operation delete this element. In a max priority queue, the find operation finds the element with maximum priority, while the delete operation delete this element. 9.1 Introduction ADT of a max priority queue AbstractDataType MaxPriorityQueue{ instances finite collection of elements,each has a priority operations create(): create an empty priority queue Size(): return number of element in the queue Max(): return element with maximum priority Insert(x): insert x into queue DeleteMax(x):delete the element with largest priority from the queue;return it in x; } 9.2 Linear List Representation Use an unordered linear list Insertions are performed at the right end of the list, θ(1) A deletion requires a search for the element with largest priority, θ(n) 9.3 Heaps 1.definition: A max heap(min Heap) is A complete binary tree The value in each node is greater(less) than or equal to those in its children(if any). 9.3 Heaps For example:an max heap k={87,78,53,45,65,09,31,17,23} 9.3 Heaps Example of min heap k={09,17,65,23,45,78,87,53,31} 9.3 Heaps 2.class MaxHeap Data member of heap: T * heap; int MaxSize, currentSize templateclass Tclass Maxheap { public: MaxHeap(int MaxHeapSize=10); ~MaxHeap(){delete[]heap;} int size()const{return currentSize;} 9.3 Heaps T Max(){if (CurrentSize==0)throw OutOfBounds(); return heap[1];} MaxHeapTinsert(const Tx); MaxHeapT DeleteMax(T x); void initialize(T a[], int size, int ArraySize); private: int CurrentSize, MaxSize; T * heap; } 9.3 Hea