removing the item with minimum key let us now turn to method remove min of the priority queue adt we know that an entry with the smallest key is stored at the root of (even if there is more than one entry with smallest keyhoweverin general we cannot simply delete node rbecause this would leave two disconnected subtrees insteadwe ensure that the shape of the heap respects the complete binary tree property by deleting the leaf at the last position of defined as the rightmost position at the bottommost level of the tree to preserve the item from the last position pwe copy it to the root (in place of the item with minimum key that is being removed by the operationfigure and illustrates an example of these stepswith minimal item ( ,cbeing removed from the root and replaced by item ( , from the last position the node at the last position is removed from the tree down-heap bubbling after removal we are not yet donehoweverfor even though is now completeit likely violates the heap-order property if has only one node (the root)then the heap-order property is trivially satisfied and the algorithm terminates otherwisewe distinguish two caseswhere initially denotes the root of if has no right childlet be the left child of otherwise ( has both children)let be child of with minimal key if key <kc the heap-order property is satisfied and the algorithm terminates if instead kc then we need to restore the heap-order property this can be locally achieved by swapping the entries stored at and (see figure and it is worth noting that when has two childrenwe intentionally consider the smaller key of the two children not only is the key of smaller than that of pit is at least as small as the key at ' sibling this ensures that the heap-order property is locally restored when that smaller key is promoted above the key that had been at and that at ' sibling having restored the heap-order property for node relative to its childrenthere may be violation of this property at chencewe may have to continue swapping down until no violation of the heap-order property occurs (see figure - this downward swapping process is called down-heap bubbling swap either resolves the violation of the heap-order property or propagates it one level down in the heap in the worst casean entry moves all the way down to the bottom level (see figure thusthe number of swaps performed in the execution of method remove min isin the worst caseequal to the height of heap that isit is log nby proposition