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 abandon the idea of storing entries in list and take the approach of storing entries in binary tree instead the heap data structure heap (see figure is binary tree that stores collection of entries at its nodes 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 nodes of itself we assume that total order relation on the keys is givenfor exampleby comparator the relational property of tdefined in terms of the way keys are storedis the followingheap-order propertyin heap tfor every node 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 an external node of are in nondecreasing order alsoa minimum key is always stored at the root of this is the most important key and is informally said to be "at the top of the heap"hencethe name "heapfor the data structure by 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 java if we define our comparator to indicate the opposite of the standard total order relation between keys (so thatfor examplecompare( , )then the root of the heap stores the largest key this versatility comes essentially "for freefrom our use of the comparator pattern by defining the minimum key in terms of the comparatorthe "minimumkey with "reversecomparator is in fact the largest figure example of heap storing entries with integer keys the last node is the one storing entry (