 # Binary Heaps (With code in C, C++, and Java)

## Introduction

A binary heap is a complete binary tree and possesses an interesting property called a heap property. The heap property states that every node in a binary tree must follow a specific order. There are two types of heaps depending upon how the nodes are ordered in the tree.

1. max-heap: In max-heap, a parent node is always larger than or equal to its children nodes.
2. min-heap: In min-heap, a parent node is always smaller than or equal to its children nodes.

Figure 1 shows an example of a max and min heap. Since binary heap is a complete binary tree, the height of the tree is always O(log n). This is very important because most of the operations we perform in the binary heap scan the tree from top to bottom or bottom to top which leads to complexity of O(log n). This helps us to efficiently implement one sorting algorithm called heap sort and a priority queue.

A binary heap can be efficiently implemented using an array (static or dynamic). To implement a binary heap of height h, we need O(2h) memory blocks and we insert the items in the array following level-order (breadth first) of a tree. Figure 2 shows the array implementation of a tree shown in Figure 1 (left). The parent, the left child, and the right of a node at i can be calculated as

• Parent = (i - 1) / 2 (Take floor).
• Left Child = 2*i + 1
• Right Child = 2*i + 2

## Operations on a binary heap

The various operations on a binary heap are given in detail below. Please note that I am describing the max-heap here but with a little modification this can be changed to min-heap.

### Insertion

The new item is initially inserted at the end of the heap (at the last position of the array). If it satisfies the heap property then we are done. Otherwise, we shift it up in the tree as long as it violates the heap property. The algorithm for inserting is given below.

```1. Insert the new item at the end of the heap.
2. Compare the newly inserted item with its parent.
If the parent is larger, stop. If the parent is smaller,  swap the item with its parent.
3. Repeat step 2 until the parent is larger or equal to the item.
```

Figure 3 shows the steps of inserting an item in an example heap. In order to insert a new item, in the worst case, we need to travel all the way to the root item. Therefore, the complexity of the insertion operation is O(log n).

### Delete Max

In a max heap, the first item is always the maximum. So to delete the maximum, we delete the first item. After the deletion of the first time, we replace the vacant first position by the last time in the array. We might need to shift this item down in order to keep the heap property intact. The algorithm is given below.

```1. Store the first time in the tree in some temporary variable.
2. Replace the first node with the item in the last node.
3. Check the first node with its children nodes.
If the left child is larger, we swap it with the left child.
If the right node is larger, we swap it with the right node.
4. Repeat step 3 until the parent node is larger than the left and right child node.
5. Return the maximum value (stored in the temporary variable).
```

Step 3 and 4 in the above algorithm is called a max heapify (or bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down). This step moves the item down in the tree to its appropriate place. Figure 4 shows an example of this process. As the insertion step, the complexity of delete max operation is O(log n).

## Building a heap

We can build the heap from an array of n items using two methods. In the first method, we successively perform the insert operation on the heap. In n insert operations, we can build the heap from the array. Since each insert operation takes O(log n) time and there are n such operations, the complexity of this method is O(nlog n).

Another method does this in linear time. In this method, the internal node of the tree is max-heapified one at a time. If there are n items in the array, we start from the item at n/2 position and heapify it and we move to next item and do the same all the way down to the first item in the array. Consider a tree given in figure 5. There are 10 nodes in the tree. Since the tree is a complete binary tree there are n/2 (floor) leaf nodes. We ignore all the leaf nodes and heapify the internal nodes. Using this method, we can build the heap in linear time O(n). The algorithm for this method is given below.

```build-max-heap(arr) {
n = length of arr;
for (i = n/2; i > 0; i--) {
max-heapify(arr, i);
}
}
```

## Implementation

The implementation of heap in C, C++, and Java is given below.