## Preliminaries we need to know for Heap

A binary tree is a collection of elements called nodes. The collection is either empty or it consists of a node called the root, along with two binary trees called the left and right subtrees. The roots of the left and right subtrees are children of the root; the root is the parent of these children. An edge connects each node of a binary tree to each of its children. A node with no children is called a leaf. A node having at least one child is called an internal node. An example binary tree is shown below in Figure.

An example binary tree. Node 0 is the root of the tree. Nodes 1 and 2 are the root's children. Node 1 is the root of node 0's left subtree. Node 4 is the root of node 1's right subtree. Node 4's right subtree is the empty tree. Nodes 3, 5, 7, 8, and 9 are leaves.

The depth of node n in a binary tree is the number of edges that must be traversed when traveling from the root of the tree to n. The height of the tree is one more than the depth of the deepest node. All nodes with depth d are said to be at level d of the tree. A binary tree is called complete if it was built by filling its levels from left to right, starting at the root. The tree of Figure 6.1 is not complete. An example complete binary tree is shown below in Figure

A complete binary tree. In a complete binary tree of height h, all levels are full except perhaps level h - 1.

Algorithm 12 Heap 12