Write a c program for min heap. For example you are given a list of numbers 9 8 -6 3 1 -5 then write c program to make min heap. The program should support push and pop operation on min heap. For basic understanding read this link http://wikistack.com/max-heap-and-min-heap/. Bellow figure is binary tree visualization of min heap after inserting 9,8,-6,3,1 and -5.

c program for min heapHow to write c program for min heap

  • Create data structure for min heap.
/* heap data structure */
struct heap
{
  int *data; // array to hold node value
  int capacity; // capacity of min heap
  int node_index; // index of node 
};
struct heap ds;
  • Initialize the heap data structure. here we will allocate size of the data array and the node_index. Look at below code it is a self explanatory.
void init (int size)
{
  ds.data = (int *) malloc (sizeof (int) * size);
  int i = 0;
  for (i = 1; i < size; i++)
    ds.data[i] = INT_MAX;

  ds.capacity = size;
  ds.node_index = 0;
}
  • 1 based array indexing. we will store root node of the min binary tree heap at index 1. min heap is a complete binary tree where each node value is greater than or equal to it’s child node. If we will use 1-based array index then the formulas become the simpler n/2 (parent node index), 2n(left child index) and 2n + 1( right child index).
/* get left child index */
int getLetf (int index)
{
  return 2 * index;
}

/* get right child index */
int getRight (int index)
{
  return 2 * index + 1;
}

/* get parent index */
int getParent (int index)
{
  return (index / 2);
}

Push or insert operation

  • At this stage we need to focus more with an example. Let us see below figure , it is already a min heap [-6 1 8 9 3], Now let us push or insert -5

c program for min heap step 1.pngAppend the new value -5 to the end of the data array [-6,1,8,9,3] -5.

c program for min heap step 2.pngFrom above figure we can see easily that heap property is violated at new node index 6. So what we do? we restore the min heap property by swapping the value of child node to the parent node because the value of child node at index 6 is less than its parent node 3.  we continue this step until min heap property restoration.

c program for min heap step 3.pngRemove or pop operation on min heap.

  • copy the last element of the array into the first element of the array.
  • decrease the node_index ( i.e array size ).
  • restore the min heap property. After placing the last array element to first array element , heap  property would be broken. In this case we have to find min index by comparing the root index with left child and right child.  Look at the code it will be easy to understand.

Here is complete sample code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>

/* heap data structure */
struct heap
{
  int *data;
  int capacity;
  int node_index;
};
struct heap ds;

void init (int size)
{
  ds.data = (int *) malloc (sizeof (int) * size);
  int i = 0;
  for (i = 1; i < size; i++)
    ds.data[i] = INT_MAX;

  ds.capacity = size;
  ds.node_index = 0;
}

/* get left child index */
int getLetf (int index)
{
  return 2 * index;
}

/* get right child index */
int getRight (int index)
{
  return 2 * index + 1;
}

/* get parent index */
int getParent (int index)
{
  return (index / 2);
}

void heapyfy_push (int index)
{
  if (index >= ds.capacity)
    return;
  int parentNodeIndex = getParent (index);
  int tmp;
  if (index != 1)
    {
      if (ds.data[parentNodeIndex] > ds.data[index])
	{
	  tmp = ds.data[parentNodeIndex];
	  ds.data[parentNodeIndex] = ds.data[index];
	  ds.data[index] = tmp;
	  heapyfy_push (parentNodeIndex);
	}
    }
}

void push (int value)
{
  ds.node_index++;
  // check if heap is full or not full
  if (ds.node_index < ds.capacity)
    {
      ds.data[ds.node_index] = value;
      heapyfy_push (ds.node_index);
    }
  else
    {
      printf ("Heap is full\n");
      printf ("Not possible to push %d\n", value);
      exit (-1);
    }
}

void heapyfy_pop (int index)
{
  int tmp;
  int left = getLetf (index);
  int right = getRight (index);
  int min_index;
  if (right >= ds.node_index)
    {
      if (left >= ds.node_index)
	return;
      else
	min_index = left;
    }
  else
    {
      if (ds.data[left] <= ds.data[right])
	min_index = left;
      else
	min_index = right;
    }
  if (ds.data[index] > ds.data[min_index])
    {
      tmp = ds.data[min_index];
      ds.data[min_index] = ds.data[index];
      ds.data[index] = tmp;
      heapyfy_pop (min_index);
    }
}

int pop ()
{
  int minvalue;
  if (!isEmpty ())
    {
      minvalue = ds.data[1];
      ds.data[1] = ds.data[ds.node_index];
      ds.node_index--;
      if (ds.node_index > 1)
	heapyfy_pop (1);

      return minvalue;
    }

}

void cleanMemory ()
{
  free (ds.data);
}

int isEmpty ()
{
  if (ds.node_index == 0)
    return 1;
  else
    return 0;
}

void printHeap ()
{
  int i = 1;
  for (i; i <= ds.node_index; i++)
    printf ("%d ", ds.data[i]);
  printf ("\n");

}// test heap
int main ()
{
  // the capacity of heap will be 6
  // we need to init with 6 + 1 size,becuase we have
  // chosen 1 based array for storage
  init (7);
  push (9);
  push (8);
  push (-6);
  push (3);
  push (1);
  printf ("heap after pusshing 9 8 -6 3 1 -5\n");
  printHeap ();
  pop ();
  printf ("heap array after pop \n");
  printHeap ();
  push (2);
  printf ("heap array after pushing 2\n");
  printHeap ();
  cleanMemory ();
  return 0;
}

Ref:

https://en.wikipedia.org/wiki/Binary_heap



Related Contents to follow