heaps the two strategies for implementing priority queue adt in the previous section demonstrate an interesting trade-off when using an unsorted list to store entrieswe can perform insertions in ( timebut finding or removing an element with minimum key requires an ( )-time loop through the entire collection in contrastif using sorted listwe can trivially find or remove the minimum element in ( timebut adding new element to the queue may require (ntime to restore the sorted order in this sectionwe provide more efficient realization of priority queue using data structure called binary heap this data structure allows us to perform both insertions and removals in logarithmic timewhich is significant improvement over the list-based implementations discussed in section the fundamental way the heap achieves this improvement is to use the structure of binary tree to find compromise between elements being entirely unsorted and perfectly sorted the heap data structure heap (see figure is binary tree that stores collection of items at its positions and that satisfies two additional propertiesa relational property defined in terms of the way keys are stored in and structural property defined in terms of the shape of itself the relational property is the followingheap-order propertyin heap for every position other than the rootthe key stored at is greater than or equal to the key stored at ' parent as consequence of the heap-order propertythe keys encountered on path from the root to leaf of are in nondecreasing order alsoa minimum key is always stored at the root of this makes it easy to locate such an item when min or remove min is calledas it is informally said to be "at the top of the heap(hencethe name "heapfor the data structureby the waythe heap data structure defined here has nothing to do with the memory heap (section used in the run-time environment supporting programming language like python for the sake of efficiencyas will become clear laterwe want the heap to have as small height as possible we enforce this requirement by insisting that the heap satisfy an additional structural property--it must be what we term complete complete binary tree propertya heap with height is complete binary tree if levels of have the maximum number of nodes possible (namelylevel has nodesfor < < and the remaining nodes at level reside in the leftmost possible positions at that level