Problem statement: Given a Binary Heap, perform the operations Delete() , Decreasekey() and BuildHeap().
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
BuildHeap():
Given an array of integers, we should build the Binary Heap (Min Heap) from the given array.
Example :
Input: arr[] = {9,3,2,5,4,6,7,8,1}
Output: arr[]= {1,3,2,5,4,6,7,8,9}
In a Binary Heap having N nodes.
The Range of leaf nodes in its array representation is from (N/2)th index to (N-1)th index.
The Range of Internal Node is 0th index to (N/2 -1)th index.
Approach:
- If we observe that the binary tree formed from the given array of integers doesn’t form a Binary Heap (Min Heap). The idea is to Heapify the Complete Binary tree formed from the array in reverse level order.
- Heapify can only be called at index i, if all the subtrees of the tree rooted at index i, are valid binary Heap.
- But We may not sure that all subtrees are binary Heap. So we start from the last Node and call heapify on it and make it a valid binary heap, and move on to the second last Node, and so on.
- By following the above approach, we can ensure that for index i, all the subtrees of the tree rooted at i, are binary heaps, So we can call the heapify function on it.
- If We clearly see the leaf Nodes are always binary heaps, So calling heapify on them is waste of time. So start calling heapify from the last Non-leaf Node, and perform the heapify, Operation of each non-leaf node in reverse level order.
| Heapify on 5 : |  Swap 1 and 5 | |
| Heapify on 2 : |  2 < 6 and 2 < 7, Heap property satisfied | |
| Heapify on 3 : |  Swap 1 and 3 |  3 < 5 and 3 < 8, Heap property satisfied. |
| Heapify on 9: |  Swap 9 and 1 |  Swap 3 and 9 |
 Swap 9 and 5 |  9 is a leaf node Heap property Satisfied. |
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void Heapify(int arr[], int i, int n) {
int ri = 2 * i + 2; /*right child*/
int li = 2 * i + 1; /*left child*/
int smallest = i; /*intially assume violated value in Min value*/
if (li < n && arr[li] < arr[smallest])
smallest = li;
if (ri < n && arr[ri] < arr[smallest])
smallest = ri;
/*smallest will store the minvalue index*/
/*If the Minimum among the three nodes is the parent itself,
that is Heap property satisfied so stop else call function recursively on Minvalue node*/
if (smallest != i) {
swap(arr[i], arr[smallest]);
Heapify(arr, smallest, n);
}
}
void print(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {9, 3, 2, 5, 4, 6, 7, 8, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int lastnonleaf = n / 2 - 1;
for (int i = lastnonleaf; i >= 0; i--)
Heapify(arr, i, n);
print(arr, n);
return 0;
}Output: 1 3 2 5 4 6 7 8 9
Time Complexity : O(N)
Java Code
import java.util.*;
class TUF {
static void Heapify(int arr[], int i, int n) {
int ri = 2 * i + 2; /*right child*/
int li = 2 * i + 1; /*left child*/
int smallest = i; /*intially assume violated value in Min value*/
if (li < n && arr[li] < arr[smallest])
smallest = li;
if (ri < n && arr[ri] < arr[smallest])
smallest = ri;
/*smallest will store the minvalue index*/
/*If the Minimum among the three nodes is the parent itself,
that is Heap property satisfied so stop else call function recursively on Minvalue node*/
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
Heapify(arr, smallest, n);
}
}
static void print(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {9, 3, 2, 5, 4, 6, 7, 8, 1};
int n = arr.length;
int lastnonleaf = n / 2 - 1;
for (int i = lastnonleaf; i >= 0; i--)
Heapify(arr, i, n);
print(arr, n);
}
}Output: 1 3 2 5 4 6 7 8 9
Time Complexity : O(N)
Decreasekey() :
- Given an index and a value, we need to update the value at the index with the given value. We assume that the given value is less than the existing value at that index.
Steps to be followed for Decreasekey():
- Let’s the index be i and the value be new_val. Update existing value at index i with new_val i.e arr[i] = new_val.
- By performing the above step, the Complete binary tree property is not violated, but the Min heap property may get violated.
- As the new_val we are inserting is less than the previously existing value, the min-heap property is not violated in subtrees of this rooted tree.
- It may get violated in its ancestors, so as we do in insert operation, check the value of a current node with its parent node, if it violates the min-heap property
Swap the nodes and recursively do the same.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class BinaryHeap {
public:
int capacity; /*Maximum elements that can be stored in heap*/
int size; /*Current no of elements in heap*/
int * arr; /*array for storing the keys*/
BinaryHeap(int cap) {
capacity = cap; /*Assigning the capacity*/
size = 0; /*Intailly size of hepa is zero*/
arr = new int[capacity]; /*Creating a array*/
}
/*returns the parent of ith Node*/
int parent(int i) {
return (i - 1) / 2;
}
/*returns the left child of ith Node*/
int left(int i) {
return 2 * i + 1;
}
/*Returns the right child of the ith Node*/
int right(int i) {
return 2 * i + 2;
}
/*Insert a new key x*/
void Insert(int x) {
if (size == capacity) {
cout << "Binary Heap Overflwon" << endl;
return;
}
arr[size] = x; /*Insert new element at end*/
int k = size; /*store the index ,for checking heap property*/
size++; /*Increase the size*/
/*Fix the min heap property*/
while (k != 0 && arr[parent(k)] > arr[k]) {
swap( & arr[parent(k)], & arr[k]);
k = parent(k);
}
}
void Decreasekey(int i, int val) {
arr[i] = val; /*Updating the new_val*/
while (i != 0 && arr[parent(i)] > arr[i]) /*Fixing the Min heap*/ {
swap( & arr[parent(i)], & arr[i]);
i = parent(i);
}
}
int getMin() {
return arr[0];
}
void swap(int * x, int * y) {
int temp = * x;
* x = * y;
* y = temp;
}
};
int main()
{
BinaryHeap h(20);
h.Insert(4);
h.Insert(1);
h.Insert(2);
h.Insert(6);
h.Insert(7);
h.Insert(3);
h.Insert(8);
h.Insert(5);
cout << "Min value is " << h.getMin() << endl;
h.Decreasekey(3, -1);
cout << "Min value is " << h.getMin() << endl;
return 0;
}Output:
Min value is 1
Min value is -1
Explanation: Initially Minimum value is 1, after decreasing the value at the 3rd index i.e 4 to -1, the New minimum value is -1.
Time Complexity : O(logN)
Java Code
import java.util.*;
class BinaryHeap {
static int capacity; /*Maximum elements that can be stored in heap*/
static int size; /*Current no of elements in heap*/
static int arr[]; /*array for storing the keys*/
BinaryHeap(int cap) {
capacity = cap; /*Assigning the capacity*/
size = 0; /*Intailly size of hepa is zero*/
arr = new int[capacity]; /*Creating a array*/
}
/*returns the parent of ith Node*/
static int parent(int i) {
return (i - 1) / 2;
}
/*returns the left child of ith Node*/
static int left(int i) {
return 2 * i + 1;
}
/*Returns the right child of the ith Node*/
static int right(int i) {
return 2 * i + 2;
}
/*Insert a new key x*/
static void Insert(int x) {
if (size == capacity) {
System.out.println("Binary Heap Overflown");
return;
}
arr[size] = x; /*Insert new element at end*/
int k = size; /*store the index ,for checking heap property*/
size++; /*Increase the size*/
/*Fix the min heap property*/
while (k != 0 && arr[parent(k)] > arr[k]) {
int temp = arr[parent(k)];
arr[parent(k)] = arr[k];
arr[k] = temp;
k = parent(k);
}
}
static void Heapify(int ind) {
int ri = right(ind); /*right child*/
int li = left(ind); /*left child*/
int smallest = ind; /*intially assume violated value in Min value*/
if (li < size && arr[li] < arr[smallest])
smallest = li;
if (ri < size && arr[ri] < arr[smallest])
smallest = ri;
/*smallest will store the minvalue index*/
/*If the Minimum among the three nodes is the parent itself,
that is Heap property satisfied so stop else call function recursively on Minvalue node*/
if (smallest != ind) {
int temp = arr[ind];
arr[ind] = arr[smallest];
arr[smallest] = temp;
Heapify(smallest);
}
}
static int getMin() {
return arr[0];
}
static void Decreasekey(int i, int val) {
arr[i] = val; /*Updating the new_val*/
while (i != 0 && arr[parent(i)] > arr[i]) /*Fixing the Min heap*/ {
int temp = arr[parent(i)];
arr[parent(i)] = arr[i];
arr[i] = temp;
i = parent(i);
}
}
public static void main(String args[])
{
BinaryHeap h = new BinaryHeap(20);
h.Insert(4);
h.Insert(1);
h.Insert(2);
h.Insert(6);
h.Insert(7);
h.Insert(3);
h.Insert(8);
h.Insert(5);
System.out.println("Min value is " + h.getMin());
h.Decreasekey(3, -1);
System.out.println("Min value is " + h.getMin());
}
}Output:
Min value is 1
Min value is -1
Explanation: Initially Minimum value is 1, after decreasing the value at the 3rd index i.e 4 to -1, the New minimum value is -1.
Time Complexity : O(logN)
Delete() :
- Given an index,delete the value at that index from min-heap.
Steps to be followed for Delete operation():
- First, update the value at the index that needs to be deleted with INT_MIN.
- Now call the Decreasekey() function at the index which is need to be deleted.
- As the value at the index is the least, it reaches the top.
- Now call the ExtractMin() operation which deletes the root node in Minheap.
- In this way, the desired index value is deleted from the Minheap.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class BinaryHeap {
public:
int capacity; /*Maximum elements that can be stored in heap*/
int size; /*Current no of elements in heap*/
int * arr; /*array for storing the keys*/
BinaryHeap(int cap) {
capacity = cap; /*Assigning the capacity*/
size = 0; /*Intailly size of hepa is zero*/
arr = new int[capacity]; /*Creating a array*/
}
/*returns the parent of ith Node*/
int parent(int i) {
return (i - 1) / 2;
}
/*returns the left child of ith Node*/
int left(int i) {
return 2 * i + 1;
}
/*Returns the right child of the ith Node*/
int right(int i) {
return 2 * i + 2;
}
/*Insert a new key x*/
void Insert(int x) {
if (size == capacity) {
cout << "Binary Heap Overflwon" << endl;
return;
}
arr[size] = x; /*Insert new element at end*/
int k = size; /*store the index ,for checking heap property*/
size++; /*Increase the size*/
/*Fix the min heap property*/
while (k != 0 && arr[parent(k)] > arr[k]) {
swap( & arr[parent(k)], & arr[k]);
k = parent(k);
}
}
void Heapify(int ind) {
int ri = right(ind); /*right child*/
int li = left(ind); /*left child*/
int smallest = ind; /*intially assume violated value in Min value*/
if (li < size && arr[li] < arr[smallest])
smallest = li;
if (ri < size && arr[ri] < arr[smallest])
smallest = ri;
/*smallest will store the minvalue index*/
/*If the Minimum among the three nodes is the parent itself,
that is Heap property satisfied so stop else call function recursively on Minvalue node*/
if (smallest != ind) {
swap( & arr[ind], & arr[smallest]);
Heapify(smallest);
}
}
int getMin() {
return arr[0];
}
int ExtractMin() {
if (size <= 0)
return INT_MAX;
if (size == 1) {
size--;
return arr[0];
}
int mini = arr[0];
arr[0] = arr[size - 1]; /*Copy last Node value to root Node value*/
size--;
Heapify(0); /*Call heapify on root node*/
return mini;
}
void Decreasekey(int i, int val) {
arr[i] = val; /*Updating the new_val*/
while (i != 0 && arr[parent(i)] > arr[i]) /*Fixing the Min heap*/ {
swap( & arr[parent(i)], & arr[i]);
i = parent(i);
}
}
void Delete(int i) {
Decreasekey(i, INT_MIN);
ExtractMin();
}
void swap(int * x, int * y) {
int temp = * x;
* x = * y;
* y = temp;
}
};
int main()
{
BinaryHeap h(20);
h.Insert(4);
h.Insert(1);
h.Insert(2);
h.Insert(6);
h.Insert(7);
h.Insert(3);
h.Insert(8);
h.Insert(5);
cout << "Min value is " << h.getMin() << endl;
h.Delete(0);
cout << "Min value is " << h.getMin() << endl;
return 0;
}Output:
Min value is 1
Min value is 2
Explanation: Initially Minimum value is 1, after deleting the 0th node i.e 1, the new minimum is 2.
Java Code
import java.util.*;
class BinaryHeap {
static int capacity; /*Maximum elements that can be stored in heap*/
static int size; /*Current no of elements in heap*/
static int arr[]; /*array for storing the keys*/
BinaryHeap(int cap) {
capacity = cap; /*Assigning the capacity*/
size = 0; /*Intailly size of hepa is zero*/
arr = new int[capacity]; /*Creating a array*/
}
/*returns the parent of ith Node*/
static int parent(int i) {
return (i - 1) / 2;
}
/*returns the left child of ith Node*/
static int left(int i) {
return 2 * i + 1;
}
/*Returns the right child of the ith Node*/
static int right(int i) {
return 2 * i + 2;
}
/*Insert a new key x*/
static void Insert(int x) {
if (size == capacity) {
System.out.println("Binary Heap Overflown");
return;
}
arr[size] = x; /*Insert new element at end*/
int k = size; /*store the index ,for checking heap property*/
size++; /*Increase the size*/
/*Fix the min heap property*/
while (k != 0 && arr[parent(k)] > arr[k]) {
int temp = arr[parent(k)];
arr[parent(k)] = arr[k];
arr[k] = temp;
k = parent(k);
}
}
static void Heapify(int ind) {
int ri = right(ind); /*right child*/
int li = left(ind); /*left child*/
int smallest = ind; /*intially assume violated value in Min value*/
if (li < size && arr[li] < arr[smallest])
smallest = li;
if (ri < size && arr[ri] < arr[smallest])
smallest = ri;
/*smallest will store the minvalue index*/
/*If the Minimum among the three nodes is the parent itself,
that is Heap property satisfied so stop else call function recursively on Minvalue node*/
if (smallest != ind) {
int temp = arr[ind];
arr[ind] = arr[smallest];
arr[smallest] = temp;
Heapify(smallest);
}
}
static int getMin() {
return arr[0];
}
static int ExtractMin() {
if (size <= 0)
return Integer.MAX_VALUE;
if (size == 1) {
size--;
return arr[0];
}
int mini = arr[0];
arr[0] = arr[size - 1]; /*Copy last Node value to root Node value*/
size--;
Heapify(0); /*Call heapify on root node*/
return mini;
}
static void Decreasekey(int i, int val) {
arr[i] = val; /*Updating the new_val*/
while (i != 0 && arr[parent(i)] > arr[i]) /*Fixing the Min heap*/ {
int temp = arr[parent(i)];
arr[parent(i)] = arr[i];
arr[i] = temp;
i = parent(i);
}
}
static void Delete(int i) {
Decreasekey(i, Integer.MIN_VALUE);
ExtractMin();
}
public static void main(String args[])
{
BinaryHeap h = new BinaryHeap(20);
h.Insert(4);
h.Insert(1);
h.Insert(2);
h.Insert(6);
h.Insert(7);
h.Insert(3);
h.Insert(8);
h.Insert(5);
System.out.println("Min value is " + h.getMin());
h.Delete(0);
System.out.println("Min value is " + h.getMin());
}
}Output:
Min value is 1
Min value is 2
Explanation: Initially Minimum value is 1, after deleting the 0th node i.e 1, the new minimum is 2.
Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article