The Heap Data StructureOverviewPriority QueueWorst case time complexity for heapsDepth of tree nodesHeight of tree nodesA full binary treeA full binary tree - cont.A complete binary treeHeight (depth) of a complete binary treeDefinition of a heapSlide 12Methodsinsert(v)Percolate Start at index to Reestablish MinHeap PropertyTime analysis for Percolate(index)Slide 17percolate(last)deleteMin()Delete minimumSiftDown(bt, i)Time analysis for Siftdown(i)Slide 23Slide 24Slide 25Building a Heap: Method 1Slide 27Slide 28Slide 29Slide 30Slide 31Time for slow make heapWhy isSlide 34Build the Heap:Method 2Slide 36Slide 37Slide 38Slide 39Slide 40ExampleSlide 42Tight analysis of Method 2Cost of fast make heapThe total costSlide 46Improved Build the Heap:Method 2Leaves and “parents” in a Complete Binary TreeHEAPSORT(A)DECREASE-KEY(bt, i, key)The Heap Data Structure01/14/19 Cutler Heap 2OverviewOverview•Usage of a heap–Priority queue–HeapSort•Definitions: height, depth, full binary tree, complete binary tree•Definition of a heap•Methods of a heap01/14/19 Cutler Heap 3Priority Queue•A priority queue is a collection of zero or more items,–associated with each item is a priority•Operations:– insert a new item–delete item with the highest priority–find item with the highest priority01/14/19 Cutler Heap 4Worst case time complexityfor heaps•Build heap with n items - (n)•insert() into a heap with n items - (lg n) •deleteMin() from a heap with n items- (lg n)•findMin() - (1)01/14/19 Cutler Heap 5Depth of tree nodesDepth of tree nodes•Depth of a node is:•If node is the root - 0•Otherwise - (depth of its parent + 1)•Depth of a tree is maximum depth of its leaves.0112 2A tree of depth 201/14/19 Cutler Heap 6Height of tree nodesHeight of tree nodes•Height of a node is:–If node is a leaf - 0–Otherwise - (maximum height of its children +1)•Height of a tree is the height of the root.00 012A tree of height 201/14/19 Cutler Heap 7A full binary treeA full binary tree•A full binary tree is a binary tree such that:–All internal nodes have 2 children–All leaves have the same depth d•The number of nodes is n = 2d+1 - 17 = 22+1 - 1A full binary tree of depth = height = 201/14/19 Cutler Heap 8A full binary tree - cont. A full binary tree - cont. •Number the nodes of a full binary tree of depth d: •The root at depth 0 is numbered - 1•The nodes at depth 1, …, d are numbered consecutively from left to right, in increasing depth.1235 64 701/14/19 Cutler Heap 9A complete binary tree A complete binary tree •A complete binary tree of depth d and n nodes is a binary tree such that its nodes would have the numbers 1, …, n in a full binary tree of depth d.•The number of nodes 2d n  2d+1 -11235 641235 64 701/14/19 Cutler Heap 10HeightHeight (depth) of a complete (depth) of a complete binary treebinary tree• Number of nodes n satisfy: 2h  n and (n + 1) 2h+1•Taking the log base 2 we get: h  lg n and lg(n + 1)  h + 1 or lg(n + 1)-1  h  lg n• Since h is integer and lg(n + 1) -1  =  lg n h = lg(n + 1) - 1=  lg n 01/14/19 Cutler Heap 11Definition of a heapDefinition of a heap•A heap is a complete binary tree that satisfies the heap property.•Minimum Heap Property: The value stored at each node is less than or equal to the values stored at its children.–OR Maximum Heap Property: greater01/14/19 Cutler Heap 12 Heap and its (dynamic) array Heap and its (dynamic) array implementationimplementation3 28718 14 929612345 678 91011 3 2 8 7 29 61 2 3 4 5 6 7 8 918 14 910lastbtroot = 1Parent(i) = i/2Left(i)=2iRight(i)=2i+101/14/19 Cutler Heap 13MethodsMethods•insert•deleteMin•percolate (or siftUp)•siftDown•buildHeap•Other methods–size, isEmpty, findMin, decreaseKey•Assume that bt is an array that is used to “store” the heap and is visible to all methods.01/14/19 Cutler Heap 14insert(insert(vv))•Item inserted as new last item in the heap–Heap property may be violated•Percolate to restore heap property30 208070 29612345 6710Lastafterinsert6last01/14/19 Cutler Heap 15Percolate Percolate Start at index to Reestablish MinHeap Propertyprocedure percolate (index ) if index >root // root = 1 p = parent(index) if bt [p].key > bt [ index ].key swap( index, p) percolate(p)The worst case growth rate of percolate is (d(index)) where d(index) denotes the depth of node index or O(lg n).01/14/19 Cutler Heap 1612345 67lg nndTime analysis for Percolate(index)(d(index))O(lg n) for index < n(lg n) for index = n01/14/19 Cutler Heap 17insert(insert(vv))insert( v )1. last =last+12. bt[last]  v //insert at new last position of tree3. percolate ( last )The worst case time of insert is (d(last)), or (lg n)01/14/19 Cutler Heap 18percolatepercolate((lastlast))30 108070 292012345 676last30 68070 292012345 6710last01/14/19 Cutler Heap 19deleteMin()•Save root object (1)•Remove last element and store in root (1)•siftDown(1)30208012 3410302012 380308012 32010lastAfter siftDown(1)01/14/19 Cutler Heap 20Delete minimum deleteMin ()1. minKeyItem = bt [root] //root = 1 2. swap(root, last)3. last = last - 1 // decrease last by 14. if (notEmpty()) // last > 1 5. siftDown(root)6. return minKeyItemWorst case time is dominated by time for siftDown(root) is (h(root)) or (lg n). h(root) denotes the height of the tree01/14/19 Cutler Heap 21SiftDown(bt, i)lC = Left[i]rC = Right[i] smallest = i//smallest = index of min{bt[i], bt[lC], bt[rC]} if (lC <= last) and (bt[lC] < bt[i]) smallest = lC if (rC <= last) and (bt[rC] < bt[smallest]) smallest = rC if (smallest != i) // Otherwise bt is already a heap swap bt[i] and bt[smallest] SiftDown(bt, smallest) //Continue to sift down01/14/19 Cutler Heap 2212345 67lg nnh Time analysis for Siftdown(i)(h(i))O(lg n) for i >1(lgn) for i=101/14/19 Cutler Heap 234 381712 14 1961312345 678 9109siftDown(1)New value at root. Satisfy the Heap property.Right Child is smallerExchange root and right child01/14/19 Cutler Heap 244 981712 14 1961312345 678 9103ParentLeft Child is smallerExchange parent and left child01/14/19 Cutler Heap 254 681712 14 1991312345 678 9103The worst case run time to do siftDown(index) is(h(index)) where h(index) is the height of node indexor O(lg n)01/14/19 Cutler Heap 26Building a Heap: Method 1•Assume that array bt has n elements, and