minimum keywhich will always be at the root of the heap 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 propertyit must be complete before we define this structural propertywe need some definitions we recall from section that level of binary tree is the set of nodes of tthat have depth given nodes and on the same level of twe say that is to the left of if is encountered before in an inorder traversal of that isthere is node of such that is in the left subtree of and is in the right subtree of for examplein the binary tree of figure the node storing entry ( ,kis to the left of the node storing entry ( qin standard drawing of binary treethe "to the left ofrelation is visualized by the relative horizontal placement of the nodes 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 in level all the internal nodes are to the left of the external nodes and there is at most one node with one childwhich must be left child by insisting that heap be completewe identify another important node in heap tother than the rootnamelythe last node of twhich we define to be the right-mostdeepest external node of (see figure the height of heap let denote the height of another way of defining the last node of is that it is the node on level such that all the other nodes of level are to the left of it insisting that be complete also has an important consequenceas shown in proposition