Priority Queues and Disjoint SetsOutlinePriority QueuesSlide 4Slide 5Slide 6Slide 7HeapsHeaps: InsertSlide 10Slide 11Slide 12Heaps: DeleteMinSlide 14Slide 15Heaps: Array ImplementationHeaps: ImplementationHeaps: sentinelSlide 19More examplesSlide 21Slide 22Slide 23Slide 24Slide 25More on Heaps: BuildHeapSlide 27More on HeapsAgendaDisjoint SetsSlide 31Up-TreesUp-Trees: UnionSlide 34Up-Trees: Union by SizeUp-Trees: FindSlide 37Slide 38Up-Trees: Array ImplementationExamples..Simple ImplementationSlide 42Slide 43Efficient ImplementationSlide 45Slide 46SummaryPriority Queues and Disjoint SetsCSCI 2720Spring 2005OutlinePriority QueuesOperations on Priority QueuesInsert, FindMin, DeleteMinHeap RepresentationMore about heaps (BuildHeap, HeapSort)Disjoint SetsOperations on Disjoint SetsUp Tree RepresentationPriority QueuesDefinition: A Priority Queue is a set ADT of such pairs (K,I) supporting the following operations where K  key, a set of linearly ordered key values and I is associated with some information of type Element. MakeEmptySet( )IsEmptySet(S)Insert(K,I,S): Add pair (K,I) to set SFindMin(S): Return an element I such that (K,I)  S and K is minimal with respect to the orderingDeleteMin(S): Delete an element (K,I) from S such that K is minimal and return IPriority QueuesThe elements have an intrinsic priority; we can Insert elements and Remove them in order of their priority, independent of the time sequence in which they were insertedNormally, the item with lowest key value is considered to have highest priorityPriority Queues are structures that are optimized for finding the minimal (= highest priority) element in the tree using FindMin( )Priority QueuesPriority Queues can be implementedusing balanced treesas a heapA double-ended Priority Queue is one which supports FindMax and DeleteMax operations along with FindMin and DeleteMin operationsPriority QueuesPartially ordered treeIt is a Key tree of elements such that the priority of each node is greater than or equal to that of each of its childrenThe highest priority element of the tree is located at the root.Tree requires reordering when the highest priority element is deleted or when a new element is inserted into the treePriority QueuesA node’s key value is <= the key value of its childrenNo conclusion can be drawn about the relative order of the items in the left and right sub-trees of a node1685912 10 5618 20HeapsAn implicitly represented complete partially ordered Key tree is called a heapEfficient structure for implementing a priority queueRun-time AnalysisFindMin(S): O(1)Insert(K,I,S): O(log n) worst-caseDeleteMin(S): O(log n)Operations on heaps to be discussedInsertDeleteMinHeaps: InsertStep 1: Append the new element in its natural position as a new leaf node in the tree and call that node xStep 2:if( x’s parent’s key > x’s key )Swap contents of x and x’s parent and reassign x to x’s parent Repeat from Step 2else Algorithm TERMINATESHeaps: InsertGiven the tree1685910 5620 181222 1344Heaps: InsertInsert node with key 771685910 5620 181222 1344168579 5620 181222 1344168597 5620 181222 1344Heaps: Insert10 10Heaps: DeleteMinStep 1: minimum_value = contents of the root node. Find the rightmost leaf on the lowest level of the tree and call that node x and copy its contents to the root node and delete the node xStep 2: Set x to point to root nodeStep 3: if (x’s key >= key of any one of x’s children)Swap contents of x and the corresponding child and reassign x to point that corresponding childRepeat from Step 3elseReturn minimum_value. Algorithm TERMINATESHeaps: DeleteMinGiven the tree below1685910 5620 181222 13441316813910 5620 181222 44Heaps: DeleteMin16138910 5620 181222 4416128910 5620 181322 44Heaps: Array ImplementationHeaps are implemented using arraysimplicit representation of the complete partial order treeEquationsLeftChild(i) = 2 iRightChild(i) = 2 i + 1Parent(i) =  i/2  1685912 10 5618 205 8 9 16 12 10 56 18 201 2 3 4 … 9Heaps: ImplementationIn practice, there is no “exchanging” of values as the proper position of an item is located by searching up the tree (insertion) or down the tree (deletion).Instead a “hole” is moved up or down the tree, by shifting the items along a path down or up single edges of the tree.The item is written only once, at the last step.Heaps: sentinelOptimization: use a sentinel valueheap[0] = sentinel, where heap is an array used to represent the heapSentinel value is a key (priority) value less than any value that could be present in the heapNow swapping with parent at the root node is also handled without any special considerationHeaps: sentinel-1Sentinel value 0 1 2 3 4 … 9 1685912 10 5618 205 8 9 16 12 10 56 18 20More examplesA Heap Applet can be seen at http://www.cs.pitt.edu/~kirk/cs1501/animations/PQueue.htmlReal code for the following operations will be discussedInsertFindMinDeleteMintemplate <class Etype>class Binary_Heap{ private: unsigned int Max_Size; // defines maximum size of the array unsigned int Size; // defines current number of elements Etype *Elements; // array that holds data public: Binary_Heap(unsigned int Initial_Size = 10); ~Binary_Heap() { delete [] Elements; } void Make_Empty() { Size=0;} int Is_Empty() const { return Size==0; } int Is_Full() const { return Size==Max_Size; } void Insert(const Etype& X); Etype Delete_Min(); Etype Find_Min() const;};heap.hHeap declaration// default constructor template <class Etype>Binary_Heap<Etype>::Binary_Heap(unsigned int Initial_Size){Size=0;Max_Size = Initial_Size; Elements = new Etype[Max_Size+1]; Assert(Elements!=NULL, "Out of space in heap constructor");Elements[0] = -1; // sentinel value}heap.cppHeap Constructor// inserts the value passed as parameter into the heap template <class Etype>void Binary_Heap<Etype>::Insert(const Etype & X) { Assert(!Is_Full(), "Priority queue is full"); unsigned int i = ++Size; // may have to resize array….while (i != 1 && Elements[i/2]>X){Elements[i]=Elements[i/2]; // swap bubble with parent i /= 2; }Elements[i]=X; // bubble, now at rest, is