At first enlighten yourself about **Heap**. Heap is a tree based data structure with heap property. Binary Heap is a very common implementation of heap data structures. Once you learn **Binary Heap** your eagerness to learn some advance Heap data structures will definitely increase. Two other advance heap data structures are **Binomial Heap** and **Fibonacci Heap**. In this article we will cover binary heap property, operations, implementation and it's possible applications.

Heap Property:IfPis a parent node ofC, then the key (the value) ofPis either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key ofC. The node at the "top" of the heap (with no parents) is called the root node.

##### Example of a Binary Max-Heap:

##### Binary Heap Properties:

**Heap Property:**It's obvious to have this property. Otherwise it won't be a heap data structure. Right ?**Shape Property:**Binary Heap is a**Complete Binary Tree**. All levels are completely filled except possibly the last level and the last level has all keys as left as possible

##### Binary Heap Operations:

Operation | Complexity |
---|---|

getMin() / peek() | `O(1)` |

extractMin() | `O(lg n)` |

insert() | `O(lg n)` |

decreaseKey() | `O(lg n)` |

delete() | `O(lg n)` |

##### Implementation:

In this section we will try to implement a **Binary Min-Heap.** As you know Binary Heap is a **Complete Binary Tree**, we can store this tree in an array. Root node resides at index ** 1**. In general if parent is in index

**, left child located at index**

`x`

**and right child located at index**

`2x`

**. Also if a node resides in index**

`2x+1`

**, parent will be**

`x`

**. So for any node**

`x/2`

**here is three utility methods to get index of parent, left child and right child.**

`x`

```
private static int parent(int i) { return (i / 2); }
private static int left(int i) { return (2 * i); }
private static int right(int i) { return (2 * i + 1); }
```

Our BinaryHeap class has three variables. ** heapArr[], heapSize and capacity**. Capacity will be provided into constructor while making instance of the class.

**will be initialized based on capacity.**

`heapArr[]`

**tracks current number of elements in binary heap.**

`heapSize`

```
static class BinaryMinHeap {
int heapArr[]; // Root node index is 1
int heapSize;
int capacity;
BinaryMinHeap(int capacity) {
this.capacity = capacity;
heapArr = new int[capacity+1];
heapSize = 0;
}
}
```

**Insert Operation:**

This is comparatively easy operation of binary heap. Add new key as a last element of tree. Then iteratively push it up based on heap property (min/max heap). As we are building min-heap if parent of node x if greater than x, swap keys of node x and it's parent and then go to parent. Do the same until heap property satisfied.

```
// Complexity: O(lg n)
public void insertItem(int item) {
if(heapSize == capacity) return;
heapSize++;
heapArr[heapSize] = item;
int currentNode = heapSize;
int parentNode = parent(currentNode);
while(currentNode != 1 && heapArr[parentNode] > heapArr[currentNode]) {
int t = heapArr[parentNode];
heapArr[parentNode] = heapArr[currentNode];
heapArr[currentNode] = t;
currentNode = parentNode;
parentNode = parent(currentNode);
}
}
```

**Get Min / Peek:**

No need to describe anything I guess. root contains desired value. Correct ?

```
// Complexity: O(1)
public int getMin() {
return heapArr[1];
}
```

**Extract Min:**

Extract min operation return minimum value of the heap (maximum value in case of max-heap) and then remove it from heap as well. To implement this operation we need another operation ** heapify(int parent)** which is the heart of binary heap. Later you will see this operation will be used in some other operations. Since we are building min-heap we will call it

**. So what it does actually ? Given a binary tree that doesn't maintain heap property it will convert the tree into proper binary heap.**

`minHeapify(int parent)`

Now lets focus to implement ** extractMin()** operation. It has only 2 steps. At first copy the key of last element of the tree into root element. Then call

`minHeapify(int index)`

to make tree into proper binary heap. First step has constant complexity **and then**

`O(1)`

**has complexity**

`minHeapify(int parent)`

**. Thus final complexity is**

`O(lg n)`

**.**

`O(lg n)`

```
// Complexity: O(lg n)
public int extractMin() {
if(heapSize == 0) return Integer.MAX_VALUE;
if(heapSize == 1) {
heapSize--;
return heapArr[1];
}
int root = heapArr[1];
heapArr[1] = heapArr[heapSize];
heapSize--;
minHeapify(1);
return root;
}
```

It's time to implement ** minHeapify(int parent)** method. As you notice this method has parameter

**which denotes from which node it will start heapify. At first it will find left and right child index and then find index of smallest (largest in case of max-heap) key among parent, left and right child. If any of left and right child contain smallest key, swap with parent and then call**

`parent`

**again with index of smallest key.**

`minHeapify(int parent)`

```
private void minHeapify(int parent) {
int l = left(parent);
int r = right(parent);
int smallest = parent;
if (l <= heapSize && heapArr[l] < heapArr[smallest]) smallest = l;
if (r <= heapSize && heapArr[r] < heapArr[smallest]) smallest = r;
if (smallest != parent) {
int t = heapArr[parent];
heapArr[parent] = heapArr[smallest];
heapArr[smallest] = t;
minHeapify(smallest);
}
}
```

**Decreasing a key:**

Consider there is a binary heap already built in and it looks like following. How about if want to decrease value of any key ? We are going to change 50 to 5. Then we need to rearrange nodes to maintain heap property. How to do that ? It's simple. Replace 50 by 5 and then pushing it up until reaches it's proper position. Here it will go up to root. `Please notice decreasing a key operation needed for min-heap and increasing a key needed in max-heap.`

```
10 5
/ \ / \
20 30 ---> 10 30
/ \ / \ / \ / \
40 50 60 70 40 20 60 70
```

```
// Complexity: O(lg n)
public void decreaseItem(int index, int newVal) {
heapArr[index] = newVal;
int parentNode = parent(index);
while(index != 1 && heapArr[parentNode] > heapArr[index]) {
int t = heapArr[parentNode];
heapArr[parentNode] = heapArr[index];
heapArr[index] = t;
index = parentNode;
parentNode = parent(index);
}
}
```

**Deleting a key:**

Deleting a key from binary heap is real tough. Just kidding !!! Actually deleting a key from binary heap requires 2 lines of code/operation. Suppose you want to delete item at index ** x**. Decrease it's value to lowest integer possible. That's

**. Since it's lowest value of all integer it will go to root position when**

`Integer.MIN_VALUE`

**execution done. Afterwards extract then root invoking**

`decreaseItem(int index, int newVal)`

**method.**

`extractMin()`

```
// Complexity: O(lg n)
public void deleteItem(int index) {
// Assign lowest value possible so that it will reach to root
decreaseItem(index, Integer.MIN_VALUE);
// Then extract min will remove that item from heap tree. correct ?
extractMin();
}
```

**Full Code:** BinaryHeap_Demo.java

##### Application of BinaryHeap:

**Priority Queue:**Any Heap data structure could be used as priority queue and priority queue is essential in some other algorithms like - BFS, Dijkstra, Huffman Coding**HeapSort: HeapSort**is very efficient sorting algorithm and binary heap could be used for heap sort.**K'th Smallest/Largest Element:**The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.