Priority QueuesAbstract Data Type: Priority QueuePriority Queues: AssumptionsImplementationsUnsorted list: ArrayUnsorted list: Linked ListSorted list: Circular ArraySorted list: Linked ListPriority Queue ImplementationsAmortized costsHeapsf00 pq 1Priority Queues•Review the abstract data type Priority Queues•Review different implementation optionsf00 pq 2Abstract Data Type: Priority Queue•A priority queue is a collection of zero or more items,–associated with each item is a priority•A priority queue has at least three operations–insert(item i) (enqueue) a new item –delete() (dequeue) the member with the highest priority–find() the item with the highest priority–decreasePriority(item i, p) decrease the priority of ith item to p•Note that in a priority queue "first in first out" does not apply in general.f00 pq 3Priority Queues: Assumptions•The highest priority can be either the minimum value of all the items, or the maximum. –We will assume the highest priority is the minimum.–Call the delete operation deleteMin().–Call the find operation findMin().•Assume the priority queue has n membersf00 pq 4Implementations•Heap. –In the worst case insert() is (lg n) and –deleteMin() is (lg n)–findMin() is (1)–decreaseKey(i, p) is (lg n)1,x2,k3,e8,d7,i9,zf00 pq 5 Unsorted list: Array1. Using an array arr. –insert() adds the new item into next empty position in arr, in (1). –findMin() is (n) in the worst case–deleteMin() is (n) in the worst case(n) to find the minimum item•and  (1) to move the last item to the position of the deleted element. –DecreasePriority(i, p) – decrease priority of ith item stored at arr[i] in (1)4,x 8,a1,b9,c7,y1 2 3450f00 pq 6Unsorted list: Linked List2. Using a linked list. –insert() in (1) with appropriate pointers. –findMin() is (n) since we may need to search the whole list.–deleteMin() is (n) •In the worst case we may need to search the whole list, (n)•Delete item, (1)f00 pq 7Sorted list: Circular Array1. A circular array A. –insert() must maintain a sorted list. (n) in the worst case •For example:The new item needs to be inserted after the item with the highest priority.So n-1 items have to be moved to make room.–findMin() is (1) – deleteMin() is (1) because the minimum item is the first one in the queue, and only the pointer to the first item needs to be changed.–DecreasePriority(i, p) – decrease priority of ith item, and reinsert (n)9,x0,b4,c7,y1 2 340firstf00 pq 8Sorted list: Linked List2. A linked list. –insert() is (n) •since in the worst case the whole list must be searched sequentially to find the location for insertion. –findMin() is (1)–deleteMin is (1) •since with appropriate pointers the first element of a linked list can be deleted in (1).f00 pq 9Priority Queue Implementations DataStructureinsertworst caseDeleteMinworst caseHeap ( lg n) ( lg n)Unsorted(array or linked list)(1) (n)Sorted(array or linked list)(n) (1)f00 pq 10Amortized costsDataStructureSequence Time AmortizedcostHeap n insert(nlgn)(lgn)Sorted n insert(n2)(n)Unsorted n/2deleteMin( n2)(n)f00 pq 11HeapsProcedure Binary heap(worst-case)Binomial heap(worst-case)Insert(lg n)O(lg n)findMin(1)O(lg n)deleteMin(lg n)O(lg n)merge(n)O(lg n)decreaseKey(lg n)O(lg