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)