implementing priority queue with heap proposition has an important consequencefor it implies that if we can perform update operations on heap in time proportional to its heightthen those operations will run in logarithmic time let us therefore turn to the problem of how to efficiently perform various priority queue methods using heap we will use the composition pattern from section to store key-value pairs as items in the heap the len and is empty methods can be implemented based on examination of the treeand the min operation is equally trivial because the heap property assures that the element at the root of the tree has minimum key the interesting algorithms are those for implementing the add and remove min methods adding an item to the heap let us consider how to perform add( ,von priority queue implemented with heap we store the pair (kvas an item at new node of the tree to maintain the complete binary tree propertythat new node should be placed at position just beyond the rightmost node at the bottom level of the treeor as the leftmost position of new levelif the bottom level is already full (or if the heap is emptyup-heap bubbling after an insertion after this actionthe tree is completebut it may violate the heap-order property henceunless position is the root of (that isthe priority queue was empty before the insertion)we compare the key at position to that of ' parentwhich we denote as if key >kq the heap-order property is satisfied and the algorithm terminates if instead kq then we need to restore the heap-order propertywhich can be locally achieved by swapping the entries stored at positions and (see figure and this swap causes the new item to move up one level againthe heap-order property may be violatedso we repeat the processgoing up in until no violation of the heap-order property occurs (see figure and the upward movement of the newly inserted entry by means of swaps is conventionally called up-heap bubbling swap either resolves the violation of the heap-order property or propagates it one level up in the heap in the worst caseupheap bubbling causes the new entry to move all the way up to the root of heap thusin the worst casethe number of swaps performed in the execution of method add is equal to the height of by proposition that bound is log