Skip to content

Instantly share code, notes, and snippets.

@dvbit
Forked from sudhanshuptl/Min_Heap.c
Created June 4, 2020 18:20
Show Gist options
  • Save dvbit/c307b6b628e5bc8d1bc92d0996cc0627 to your computer and use it in GitHub Desktop.
Save dvbit/c307b6b628e5bc8d1bc92d0996cc0627 to your computer and use it in GitHub Desktop.
Min Heap array implementation in c
/* Sudhanshu Patel sudhanshuptl13@gmail.com */
/*
Min Heap implementation in c
*/
#include<stdio.h>
#include<stdlib.h>
/*
Array Implementation of MinHeap data Structure
*/
HEAP_SIZE = 20;
struct Heap{
int *arr;
int count;
int capacity;
int heap_type; // for min heap , 1 for max heap
};
typedef struct Heap Heap;
Heap *CreateHeap(int capacity,int heap_type);
void insert(Heap *h, int key);
void print(Heap *h);
void heapify_bottom_top(Heap *h,int index);
void heapify_top_bottom(Heap *h, int parent_node);
int PopMin(Heap *h);
int main(){
int i;
Heap *heap = CreateHeap(HEAP_SIZE, 0); //Min Heap
if( heap == NULL ){
printf("__Memory Issue____\n");
return -1;
}
for(i =9;i>0;i--)
insert(heap, i);
print(heap);
for(i=9;i>=0;i--){
printf(" Pop Minima : %d\n", PopMin(heap));
print(heap);
}
return 0;
}
Heap *CreateHeap(int capacity,int heap_type){
Heap *h = (Heap * ) malloc(sizeof(Heap)); //one is number of heap
//check if memory allocation is fails
if(h == NULL){
printf("Memory Error!");
return;
}
h->heap_type = heap_type;
h->count=0;
h->capacity = capacity;
h->arr = (int *) malloc(capacity*sizeof(int)); //size in bytes
//check if allocation succeed
if ( h->arr == NULL){
printf("Memory Error!");
return;
}
return h;
}
void insert(Heap *h, int key){
if( h->count < h->capacity){
h->arr[h->count] = key;
heapify_bottom_top(h, h->count);
h->count++;
}
}
void heapify_bottom_top(Heap *h,int index){
int temp;
int parent_node = (index-1)/2;
if(h->arr[parent_node] > h->arr[index]){
//swap and recursive call
temp = h->arr[parent_node];
h->arr[parent_node] = h->arr[index];
h->arr[index] = temp;
heapify_bottom_top(h,parent_node);
}
}
void heapify_top_bottom(Heap *h, int parent_node){
int left = parent_node*2+1;
int right = parent_node*2+2;
int min;
int temp;
if(left >= h->count || left <0)
left = -1;
if(right >= h->count || right <0)
right = -1;
if(left != -1 && h->arr[left] < h->arr[parent_node])
min=left;
else
min =parent_node;
if(right != -1 && h->arr[right] < h->arr[min])
min = right;
if(min != parent_node){
temp = h->arr[min];
h->arr[min] = h->arr[parent_node];
h->arr[parent_node] = temp;
// recursive call
heapify_top_bottom(h, min);
}
}
int PopMin(Heap *h){
int pop;
if(h->count==0){
printf("\n__Heap is Empty__\n");
return -1;
}
// replace first node by last and delete last
pop = h->arr[0];
h->arr[0] = h->arr[h->count-1];
h->count--;
heapify_top_bottom(h, 0);
return pop;
}
void print(Heap *h){
int i;
printf("____________Print Heap_____________\n");
for(i=0;i< h->count;i++){
printf("-> %d ",h->arr[i]);
}
printf("->__/\\__\n");
}
sudhanshu@Unbroken:~/Github/MyCodeDump/C-Programming$ ./a.out
____________Print Heap_____________
-> 1 -> 2 -> 4 -> 3 -> 7 -> 8 -> 5 -> 9 -> 6 ->__/\__
Pop Minima : 1
____________Print Heap_____________
-> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 5 -> 9 ->__/\__
Pop Minima : 2
____________Print Heap_____________
-> 3 -> 6 -> 4 -> 9 -> 7 -> 8 -> 5 ->__/\__
Pop Minima : 3
____________Print Heap_____________
-> 4 -> 6 -> 5 -> 9 -> 7 -> 8 ->__/\__
Pop Minima : 4
____________Print Heap_____________
-> 5 -> 6 -> 8 -> 9 -> 7 ->__/\__
Pop Minima : 5
____________Print Heap_____________
-> 6 -> 7 -> 8 -> 9 ->__/\__
Pop Minima : 6
____________Print Heap_____________
-> 7 -> 9 -> 8 ->__/\__
Pop Minima : 7
____________Print Heap_____________
-> 8 -> 9 ->__/\__
Pop Minima : 8
____________Print Heap_____________
-> 9 ->__/\__
Pop Minima : 9
____________Print Heap_____________
->__/\__
__Heap is Empty__
Pop Minima : -1
____________Print Heap_____________
->__/\__
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment