C Program to Implement Binary Heap
Binary heaps are the most fundamental data structures which are used in various algorithms. They are mostly used in implementing priority queues and also in heapsort. They are tree-based data structures that satisfy heap order property. In this article, we will study the implementation of Binary heaps in C language.
What is Binary Heap in C?
A binary heap is a type of complete binary tree where each node satisfies the heap order property. There are two types of heaps based on the order: min-heaps and max-heaps.
1. Min Heaps
Every node contains the minimum value among all the nodes in its subtree.
Example: [10, 15, 30, 40, 50, 100, 40]
2. Max Heaps
Every node contains the maximum value among all the nodes in its subtree.
Example: [100, 40, 50, 10, 15, 50, 40]
Binary Heap Representation in C
In C, a binary heap is represented using an array, where for any given index i:
- The left child is at index 2 * i + 1.
- The right child is at index 2 * i + 2.
- The parent is at index (i – 1) / 2.
Operations on Binary Heap in C
Binary Heaps are optimised for the tasks that need to frequently find the maximum and minimum elements from the dataset. The common operations on binary heap are:
| S. No | Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|---|
| 1 | Insert | Adds a new element to the heap and maintains heap property. | O(log n) | O(1) |
| 2 | Extract Min/Max | Removes and returns the maximum/minimum element from the heap | O(log n) | O(1) |
| 3 | Peek | Returns the maximum element without removing it | O(1) | O(1) |
| 4 | Heapify | Maintains the heap property for a particular node and its branch. | O(log n) | O(1) |
| 5 | Delete | Removes an element at a given index and maintains heap property | O(log n) | O(1) |
| 6 | Increase/Decrease Key | Increase/Decrease the value of the already present element. | O(log n) | O(1) |
7 | Build Heap | Creates a heap from an array | O(log n) | O(1) |
Algorithm for Heapify in Min Heap
Heapify(array, size, i):
1. Set i as the largest index.
2. Calculate left child index: leftChild = 2*i + 1
3. Calculate right child index: rightChild = 2*i + 2
4. If leftChild is within the array bounds and array[leftChild] > array[largest]:
- Set leftChild as the largest index.
5. If rightChild is within the array bounds and array[rightChild] > array[largest]:
- Set rightChild as the largest index.
6. If largest is not equal to i:
- Swap array[i] and array[largest].
- Recursively call Heapify on the subtree rooted at the new largest index.
Algorithm for Building Heap using Array
It is process of creating heap data structure from a binary tree. It is used to create min or max heap. Here, we will see some steps for Heapify function
1. Consider an input array as
2. Consider it as a binary tree,
3. Apply Heapify to all the nodes from (n – 1) / 2 node to root node.
4. We get the binary tree.
Algorithm for Insertion in Min Heap
1. If the heap is empty:
- Create a new node as the root.
2. Otherwise (a node is already present):
- Insert the new node at the end (last node from left to right).
3. Heapify the array
Algorithm for Deletion in Min Heap
1. If nodeToBeDeleted is the leafNode:
- remove the node
2. Else swap nodeToBeDeleted with the lastLeafNode:
- remove noteToBeDeleted
3. heapify the array
1. Select element to be deleted
2. Swap it with last element
3. Remove last element
4. Heapify the tree
Algorithm for Peak in Min/Max Heap
This operation returns the maximum value from Max Heap and minimum value from Min Heap without deleting the node.
return arr[0]
C Program to Implement Binary Heap
We will implement min-heap in this C Program. We can also implement the max heap using minor tweaks.
// C++ program to implement the binary min heap data
// stucture using arrays
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// utility function to swap two values
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int* heap, int size, int i)
{
if (!heap) {
printf("Invalid Heap!\n");
return;
}
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
// if we are creating min heap, then we take
// the smallest element, if we are creating
// max heap, then we will take the largest element
int smallest = i;
if (leftChild < size
&& heap[leftChild] < heap[smallest]) {
smallest = leftChild;
}
if (rightChild < size
&& heap[rightChild] < heap[smallest]) {
smallest = rightChild;
}
// if the root is not the smallest, we need to swap
if (smallest != i) {
swap(heap + i, heap + smallest);
heapify(heap, size, smallest);
}
}
// building heap form the whole array
void buildHeap(int* arr, int size)
{
int start = size / 2 - 1;
for (int i = start; i >= 0; i--) {
heapify(arr, size, i);
}
}
// insert new element
void insert(int* heap, int* size, int element)
{
if (*size == MAX_SIZE) {
printf("Heap Overflow!\n");
return;
}
heap[*size] = element;
(*size)++;
int i = *size - 1;
while (i > 0) {
if (heap[(i - 1) / 2] > heap[i]) {
swap(heap + (i - 1) / 2, heap + i);
i = (i - 1) / 2;
}
else {
break;
}
}
}
// delete elements
void delete (int* heap, int* size, int index)
{
if (size == 0) {
printf("Heap Underflow\n");
return;
}
heap[index] = heap[*size - 1];
*size = *size - 1;
heapify(heap, *size, index);
}
// extract the mininmum
int extractMin(int* heap, int* size)
{
int min = heap[0];
delete (heap, size, 0);
return min;
}
// function to print heap
void printHeap(int* heap, int size)
{
// int lastInternal = size / 2 - 1;
// int curLevel;
// int nodeCount;
// int i = 0;
// while (i <= lastInternal) {
// int curLevel = log2(i + 1);
// nodeCount = 0;
// while(nodeCount != curLevel) {
// printf("%d ", heap[i + nodeCount])
// }
// print
// }
for (int i = 0; i < size; i++) {
printf("%d ", heap[i]);
}
printf("\n");
}
// driver code
int main()
{
int heap[MAX_SIZE] = { 11 };
int size = 0;
buildHeap(heap, size);
insert(heap, &size, 3);
insert(heap, &size, 2);
insert(heap, &size, 1);
insert(heap, &size, 15);
insert(heap, &size, 5);
insert(heap, &size, 4);
insert(heap, &size, 45);
printHeap(heap, size);
return 0;
}
Output
1 1 3 2 4 11 131 121 5
Contact Us