# Binary Heap: The basics & Implementations

A binary heap is a complete binary tree which has the heap property. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for heap sort.

## Complete Binary Tree

It is a kind of binary tree where all the levels, except possibly the last one are fully filled, and if the last level is not fully filled, it is filled from left to right.

## Array Representation of Binary Heap

The complete binary tree or the binary heap has an interesting property. Let’s give an index to each node of the above binary tree. The indexes will be given as level wise.

Now if we notice carefully, it can be seen that for a node at index ** i** the child nodes are at index

**and**

*2i+1***and the parent of the node is at index**

*2i+2***. Using this property the heap can be stored in an array. The root of a heap will be at index**

*floor((i-1)/2)***. So the array representation of the above binary heap will be:**

*0*Next, we’ll try to know about the heap operations. As we all know, there are two types of heap — *min-heap* and *max-heap*. For simplicity, we’ll discuss the min-heap only.

## Operations on a min-heap

There are two basic operations on a heap. The *insert* operation and the *extract* operation.

** insert operation:** With this operation, a node is added in the heap. After adding, to preserve the heap property, an

*up-heap*or

*bubble-up*or

*swim-up*or

*heapify-up*operation is performed if needed. The insertion is performed in the following manners:

**1.** Add the new node in the bottom level as the last node of the heap.**2.** Compare the added node with its parent. If the parent is smaller than the added node, stop! The heap property is reserved.**3.** And if the added node is smaller then its parent node, swap the nodes and continue from step 2.

The process is illustrated in the figure:

** Extract operation: **With this operation, the root or the minimum key of the heap is extracted or deleted. After deleting, to preserve the heap property, a

*down-heap*or

*bubble-down*or

*sink-down*or

*heapify-down*operation is performed if needed. The extraction is performed in the following manner:

**1.** Swap the root and the last node of the last level and remove the new last node.**2.** Compare the new root with the children. If the heap property is reserved, Stop!**3.** Swap the root with the smallest child and go to step 2.

The process is illustrated in the figure:

That’s it! Now we can go on and implement heap and heap operations.

## Implementing heap using C++

We are going to implement the min-heap using an array. Let’s at first do the essential things and create an integer constant *HEAP_SIZE* which will hold the maximum size of the heap. Then create an integer array *heap[HEAP_SIZE]* which will hold the heap nodes.

Now, we’ll create a global integer variable ** s**, which will hold the current size of the heap. We’ll create a function

*insert()*for inserting a new node in the heap. It’ll be added as the last node. Then we’ll do bubble-up by calling the

*bubble_up()*function. It’ll recursively call itself and will keep bubbling-up the inserted node until the heap property is reserved.

Now let’s create another function *extract()* which will extract the root. We’ll create one more function named *bubble_down() *which will recursively call itself and will keep bubbling down the swapped root until the heap property is reserved.

These are the basic operations. We can create an optional function *get_root()* which will return the minimum value i.e. the root value of the heap.

That’s it. You can find the full implementation here. Thank you very much. Let me know your thoughts.

**Note:** This is not an optimized or finely tuned implementation. This implementation needs to be tuned for some corner cases.