Home » Data Structure

Program for insertion and deletion in heap

Here, we are implementing C program that can be used to insert and delete elements in/from heap. By Manu Jemini, on January 03, 2018

What is heap?

A Heap is a widely used data structure. In that data structure, the nodes are held in a tree-like structure. A Tree-like structure means a parent node is linked with its child nodes. In below example, a parent node can have two child nodes. Nodes in a heap are linked together. The top node is called the root node or simply root.

Types of heaps

Heaps are of two type i.e. max heap and min heap. These types decide the arrangement of the nodes according to the parent-child values.

In Max-Heap, the value of the parent node is either greater than or equal to the value of child node.

In Min-Heap, the value of the parent node is either smaller than or equal to the value of child node.

Image source: https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Binary-heap.png/300px-Binary-heap.png

Above is an example of Min-Heap showing a parent node with value 1 having two child nodes with value 2 and 7, they both have their child also with different values.

The length of the array in below code is 100, one can change it for their own purpose.

C program for insertion and deletion in/from heap

#include <stdio.h>
int arr[100], n;

void display() {
  int i;
  if (n == 0) {
    printf("Heap is empty\n");
    return;
  }
  for (i = 0; i < n; i++) printf("%d ", arr[i]);
  printf("\n");
} /*End of display()*/

void insert(int num, int loc) {
  int par;
  while (loc > 0) {
    par = (loc - 1) / 2;
    if (num <= arr[par]) {
      arr[loc] = num;
      return;
    }
    arr[loc] = arr[par];
    loc = par;
  }             /*End of while*/
  arr[0] = num; /*assign num to the root node */
} /*End of insert()*/

void del(int num) {
  int left, right, i, temp, par;

  for (i = 0; i < n; i++) {
    if (num == arr[i]) break;
  }
  if (num != arr[i]) {
    printf("%d not found in heap\n", num);
    return;
  }
  arr[i] = arr[n - 1];
  n = n - 1;
  par = (i - 1) / 2; /*find parent of node i */
  if (arr[i] > arr[par]) {
    insert(arr[i], i);
    return;
  }
  left = 2 * i + 1;  /*left child of i*/
  right = 2 * i + 2; /* right child of i*/
  while (right < n) {
    if (arr[i] >= arr[left] && arr[i] >= arr[right]) return;
    if (arr[right] <= arr[left]) {
      temp = arr[i];
      arr[i] = arr[left];
      arr[left] = temp;
      i = left;
    } else {
      temp = arr[i];
      arr[i] = arr[right];
      arr[right] = temp;
      i = right;
    }
    left = 2 * i + 1;
    right = 2 * i + 2;
  }                                        /*End of while*/
  if (left == n - 1 && arr[i] < arr[left]) /* right==n */
  {
    temp = arr[i];
    arr[i] = arr[left];
    arr[left] = temp;
  }
} /*End of del()*/

int main() {
  int choice, num;
  n = 0; /*Represents number of nodes in the heap*/
  
  while (1) {
    printf("1.Insert\n");
    printf("2.Delete\n");
    printf("3.Display\n");
    printf("4.Quit\n");
    
    printf("Enter your choice : ");
    scanf("%d", &choice);
    
    switch (choice) {
      case 1:
        printf("Enter the number to be inserted : ");
        scanf("%d", &num);
        insert(num, n);
        n = n + 1;
        break;
      
      case 2:
        printf("Enter the number to be deleted : ");
        scanf("%d", &num);
        del(num);
        break;
      
      case 3:
        display();
        break;
      
      case 4:
        break;
      
      default:
        printf("Wrong choice\n");
    } /*End of switch */
  }   /*End of while */
  
  return 0;
} /*End of main()*/

Output