array-based representation of complete binary tree the array-based representation of binary tree (section is especially suitable for complete binary tree we recall that in this implementationthe elements of are stored in an array-based list such that the element at position in is stored in with index equal to the level number (pof pdefined as followsif is the root of then ( if is the left child of position qthen ( ( if is the right child of position qthen ( ( with this implementationthe elements of have contiguous indices in the range [ and the last position of is always at index where is the number of positions of for examplefigure illustrates the array-based representation of the heap structure originally portrayed in figure ( , ( , ( , ( , ( , ( , ( , ( , ( , ( , ( , ( , ( , figure an array-based representation of the heap from figure implementing priority queue using an array-based heap representation allows us to avoid some complexities of node-based tree structure in particularthe add and remove min operations of priority queue both depend on locating the last index of heap of size with the array-based representationthe last position is at index of the array locating the last position of complete binary tree implemented with linked structure requires more effort (see exercise - if the size of priority queue is not known in advanceuse of an array-based representation does introduce the need to dynamically resize the array on occasionas is done with python list the space usage of such an array-based representation of complete binary tree with nodes is ( )and the time bounds of methods for adding or removing elements become amortized (see section python heap implementation we provide python implementation of heap-based priority queue in code fragments and we use an array-based representationmaintaining python list of item composites although we do not formally use the binary tree adtcode fragment includes nonpublic utility functions that compute the level numbering of parent or child of another this allows us to describe the rest of our algorithms using tree-like terminology of parentleftand right howeverthe relevant variables are integer indexes (not "positionobjectswe use recursion to implement the repetition in the upheap and downheap utilities