《数据结构的算法在C++中的应用》（英文版）Chapter 9 Priority Queues

Chapter 9 Priority Queues

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 I)find an element 2)insert a new element 3)delete an element

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 • 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 AbstractData Type Max Priority Queue Instances finite collection of elements. each has a priority operations create(: create an empty priority queue Sizeo: 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.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, A(1) a deletion requires a search for the element with largest priority, A(n)

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 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,53456509,31,1723} 87 78 650931

9.3 Heaps • For example:an max heap k={87,78,53,45,65,09,31,17,23} 87 78 45 65 53 09 17 31 23

9.3 Heaps Example of min heap k={09,1765,2345,78875331} 09 0765 3)4578⑧7 53)(31

9.3 Heaps • Example of min heap k={09,17,65,23,45,78,87,53,31} 09 17 23 45 65 78 53 87 31

9.3 Heaps class M ahEap Data member of heap T* heap; int MaxSize, currentsize templateclass Maxheap i public MaxHeap(int MaxHeap Size=10); MaxHeapoidelete[heap int sizeOconst(return currentsize

9.3 Heaps 2.class MaxHeap Data member of heap: T * heap; int MaxSize, currentSize templateclass Maxheap { public: MaxHeap(int MaxHeapSize=10); ~MaxHeap(){delete[]heap;} int size()const{return currentSize;}

9.3 Heaps T Maxfif( Currentsize==O)throw OutofBoundso: return heap[1]; j MaxHeap &insert(const T&x) MaxHeap& deleteMax(t& x) void initialize(t all, int size, int Array Size); private int CurrentSize, Maxsize T* heap

9.3 Heaps T Max(){if (CurrentSize==0)throw OutOfBounds(); return heap[1];} MaxHeap&insert(const T&x); MaxHeap& DeleteMax(T& x); void initialize(T a[], int size, int ArraySize); private: int CurrentSize, MaxSize; T * heap; }