is terminated by user (instead of finishing normally)it must be removed from the priority queue buildheap the binary heap is sometimes constructed from an initial collection of items this constructor takes as input items and places them into heap obviouslythis can be done with successive inserts since each insert will take ( average and (log nworst-case timethe total running time of this algorithm would be (naverage but ( log nworst-case since this is special instruction and there are no other operations interveningand we already know that the instruction can be performed in linear average timeit is reasonable to expect that with reasonable care linear time bound can be guaranteed the general algorithm is to place the items into the tree in any ordermaintaining the structure property thenif percolatedown(ipercolates down from node ithe buildheap routine in figure can be used by the constructor to create heap-ordered tree the first tree in figure is the unordered tree the seven remaining trees in figures through show the result of each of the seven percolatedowns each dashed line corresponds to two comparisonsone to find the smaller child and one to compare the smaller child with the node notice that there are only dashed lines in the entire algorithm (there could have been an th--where?corresponding to comparisons to bound the running time of buildheapwe must bound the number of dashed lines this can be done by computing the sum of the heights of all the nodes in the heapwhich is the maximum number of dashed lines what we would like to show is that this sum is ( explicit binaryheapconst vector items arrayitems size )currentsizeitems sizeforint items size)++ arrayi itemsi ]buildheap)/*establish heap order property from an arbitrary arrangement of items runs in linear time *void buildheapforint currentsize -- percolatedowni )figure buildheap and constructor