A binary heap is a special kind of binary tree. Usually the word “binary” is dropped from the term and it is just called a heap. In order to explain what it is, you need to remember some of the basic facts about binary trees. Therefore, we start with a review of the required concepts.

Binary heaps are used to implement priority queues and are also used in Heap Sort to sort in O(NLogN) time. Binary heaps must have the following properties:

1. Be a complete tree (each node has at most two children)
2. Be either a Min-Heap or a Max-Heap. In a Min-Heap, the data contained in each node is less than (or equal to) the data of its children. In a Max-Heap, the data contained in each node is greater than (or equal to) the data of its children.

In this and subsequent chapter, we’ll consider the minimum element as the highest priority.

Full and Complete Binary Trees

A binary tree of height \(h\) is full, or perfect, if there are \(2^{h}\) nodes at depth \(h\). This implies that all levels less than \(h\) are full, because there could not be \(2^{h}\) nodes at depth \(h\) unless there were \(2^{h-1}\) nodes in level \(h-1\) and each had two children. The same argument applies to that level, and then to the level above it, and so on. (We could prove this by mathematical induction easily enough, but it is fairly obvious.) Since for each level \(k, 0 \leq k \leq h\), there are \(2^{k}\) nodes in that level,

A full binary tree of height h has \(1+2+2^{2}+2^{3}+\cdots+2^{h}=2^{h+1}-1\) nodes.

A binary tree of height \(h\) is complete if the tree of height \(h\)-1 rooted at its root is full, and the bottom-most level is filled from left to right. This is an informal definition. The formal one includes the requirement that, if a node at depth \(h-1\) has any children, then all nodes to the left of that node have two children, and if it has only one child, that child is a left child. Since a complete tree of height \(h\) consists of a full tree of height \(h-1\) and between 1 and \(2^{h}\) nodes in level \(h\), it follows that it has at least \(2^{h-1+1}-1+1=2^{h}\) nodes and at most \(2^{h+1}-1\) nodes.

The number of nodes in a complete binary tree of height \(h\) is at least \(2^{h}\) and at most \(2^{h+1}-1\).

Since \(\left\lfloor\log 2^{h} \mid=h\right.\) and \(\left\lfloor\log \left(2^{h+1}-1\right) \mid=h\right.\), we have proved:

Corollary 3. The height of a complete binary tree with \(n\) nodes is \(\lfloor\log n\rfloor\).

Corollary 4. In a complete binary tree with \(n\) nodes, the highest index non-leaf node is the node with index \(\lfloor(n / 2)\rfloor\).

Proof. The highest index non-leaf node has a left child and possibly a right child, and no node to its right has any children. If \(n\) is even, the last node is a left child of its parent, and the parent is the node with index \(\lfloor(n / 2)\rfloor\). (We will prove this below.) If \(n\) is odd, the last node is a right child of its parent, and the parent has index \(\lfloor(n / 2)\rfloor\) also.

Since the highest-indexed non-leaf node in a complete binary tree with \(n\) nodes has index \(\lfloor(n / 2)\rfloor\), there are \(n-\lfloor(n / 2)\rfloor\) leaf nodes in the tree. If \(n\) is even, this is \(n / 2\) exactly, and if \(n\) is odd, this is \(n / 2+1\). We have proved:

Corollary 5. In a complete binary tree with \(n\) nodes, the last \(n / 2\) nodes are leaf nodes.

The Heap Order Property

A binary tree has the heap order property if every node is smaller than or equal to its two children. Since each node has this property, it is not hard to prove by induction on the height of a node in the tree that every node is smaller than or equal to all of its descendants. A heap is a complete binary tree with the heap-order property. It follows from the definition that the root of a heap is the minimum element in the tree. Figure 1 illustrates an example of a binary heap. Notice that each node is the root of a tree with the heap order property, which means that each subtree is also a heap. Figure 2 shows a binary tree that does not have the heap-order property. The emboldened nodes are smaller than their parents.

Heaps and Arrays

A heap can be implemented easily in an ordinary array if the root is placed in index 1 instead of index 0 . As an example, consider the array below, containing the keys, \(10,15,18,23,17,20,21\), \(26 .\)

This array represents the binary tree shown in Figure 1. It is important to remember that when an array is used to represent a heap, the root is in index 1 , not \(0 .\)

With this in mind, define three functions leftchild \((k)\), rightchild \((k)\), and parent \((k)\) as follows:

• leftchild \((k)\) is the index of the left child of the node whose index is \(\mathrm{k}\),

• rightchild \((k)\) is the index of the right child of the node with index \(k\), and

• parent \((k)\) is the index of the node which is the parent of node with index \(\mathrm{k}\).

If the nodes in a complete binary tree are numbered in breadth-first order, from left to right in each level, with the root assigned index 1 , then

leftchild \((k)=2 k\) if \(k \leq n / 2\)

\(\operatorname{rightchild}(k)=2 k+1\) if \(k<n / 2\)

\(\operatorname{parent}(k)=\lfloor(k / 2)\rfloor\) if \(k>1\)

Proof. Assume that \(k\) is the index of an arbitrary node such that \(k \leq n / 2\). Suppose node \(k\) has a left child. If it has a left child, then by the definition of a complete binary tree, the entire level to the right of node \(k\) must be filled, and the entire level to the left of the left child must also be filled.

Let \(d\) be the depth of node \(k\) in the tree. There are \(2^{d}-1\) nodes in the tree above level \(d\) because a full binary tree of height \(d-1\) has \(2^{d}-1\) nodes. So how many nodes are to the left of node \(k\) in its level? It must be

\[k-\left(2^{d}-1\right)-1=k-2^{d}\]

How many nodes are to the right of \(k\) in level \(d\) ? It must be \(2^{d}\) less the number of nodes up to and including \(k\), which is

\[2^{d}-\left(k-2^{d}\right)-1=2\left(2^{d}\right)-k-1=2^{d+1}-k-1\]

Each child to the left of node \(k\) contributes 2 children in level \(d+1\) to the left of node \(k\) ‘s left child, so there are \(2\left(k-2^{d}\right)\) nodes to the left of leftchild \((k)\) in level \(d+1\). Since there are \(2^{d+1}-k-1\) nodes to the right of node \(k\) in level \(d\), the index of the left child of node \(k\) is

\[\begin{aligned} \text { leftchild }(k) &=k+\left(2^{d+1}\right)-k-1+2\left(k-2^{d}\right)+1 \\ &=2^{d+1}-1+2 k-2^{d+1}+1 \\ &=2 k \end{aligned}\]

The right child, if it exists, must have index \(2 k+1\). Finally, since le ftchild \((k)=2 k\) and rightchild \((k)=\) \(2 k+1\), it follows that parent \((k)=\lfloor k / 2\rfloor\).

This establishes that the index of a node is all we need to find its children or its parent, which means we do not need a data structure with pointers to represent a heap. This implies two important benefits of using an array to represent a heap:

• array indexing is much faster than dereferencing pointers, making access faster in general, and
• space is saved because of the absence of pointers in each node.

---

---