How to write a C Program MaxHeap and MinHeap in C Programming Language ?
Solution:
#include <stdio.h>
#include <stdlib.h>
typedef struct heap {
int dim;
int *a;
}heap;
void inizializzaArray (int *a) {
a[0] = 0;
}
void inizializzaArrayStruct (heap *h) {
h->dim = 0;
}
void stampArray (int *a) {
int i, k = 1;
for (i=1; i<=a[0]; i++) {
printf("(%d)%d ", i, a[i]);
if (i == k) {
printf("\n");
k = (i*2)+1;
}
}
printf("\n\n");
}
void stampArrayStruct (heap *h) {
int i, k = 1;
for (i=1; i<=h->dim; i++){
printf("(%d)%d ", i, h->a[i]);
if (i == k) {
printf("\n");
k = (i*2)+1;
}
}
printf("\n\n");
}
void maxHeapify (int *a) {
int i;
for (i = (a[0]+1)/2; i>=1; i--) {
int c = -1, aux, max = -1, t = i;
while(t != c){
c = t;
max = a[c];
if (( 2*c < (a[0]+1) ) && (a[c] < a[2*c])){
t = 2*c;
max = a[t];
}
if (( 2*c+1 < (a[0]+1) ) && (a[2*c + 1] > max))
t = 2*c + 1;
if ( c != t ){
aux = a[c];
a[c] = a[t];
a[t] = aux;
}
}
}
printf("Bilanciamento eseguito con successo\nL'array che mi hai passato ora è un maxHeap!!\n");
}
void maxHeapifyStruct (heap *h) {
int i;
for (i = (h->dim+1)/2; i>=1; i--) {
int c = -1, aux, max = -1, t = i;
while(t != c){
c = t;
max = h->a[c];
if (( 2*c < (h->dim+1) ) && (h->a[c] < h->a[2*c])){
t = 2*c;
max = h->a[t];
}
if (( 2*c+1 < (h->dim+1) ) && (h->a[2*c + 1] > max))
t = 2*c + 1;
if ( c != t ){
aux = h->a[c];
h->a[c] = h->a[t];
h->a[t] = aux;
}
}
}
printf("Bilanciamento eseguito con successo\nLa struct che mi hai passato ora è un maxHeap!!\n");
}
void minHeapify (int *a) {
int i;
for (i = (a[0]+1)/2; i>=1; i--) {
int c = -1, aux, max = -1, t = i;
while(t != c){
c = t;
max = a[c];
if (( 2*c < (a[0]+1) ) && (a[c] > a[2*c])){
t = 2*c;
max = a[t];
}
if (( 2*c+1 < (a[0]+1) ) && (a[2*c + 1] < max))
t = 2*c + 1;
if ( c != t ){
aux = a[c];
a[c] = a[t];
a[t] = aux;
}
}
}
printf("Bilanciamento eseguito con successo\nL'array che mi hai passato ora è un minHeap!!\n");
}
void minHeapifyStruct (heap *h) {
int i;
for (i = (h->dim+1)/2; i>=1; i--) {
int c = -1, aux, max = -1, t = i;
while(t != c){
c = t;
max = h->a[c];
if (( 2*c < (h->dim+1) ) && (h->a[c] > h->a[2*c])){
t = 2*c;
max = h->a[t];
}
if (( 2*c+1 < (h->dim+1) ) && (h->a[2*c + 1] < max))
t = 2*c + 1;
if ( c != t ){
aux = h->a[c];
h->a[c] = h->a[t];
h->a[t] = aux;
}
}
}
printf("Bilanciamento eseguito con successo\nLa struct che mi hai passato ora è un minHeap!!\n");
}
void insertKeyInMaxHeap (int k, int *a) {
if (a[0] == 0) {
a = realloc (a, 2*sizeof(int));
a[0]++;
a[a[0]] = k;
printf("L'array che mi hai passato è vuoto.\nInserisco la radice..\n");
}
else {
a = realloc (a, (a[0]+2)*sizeof(int));
a[0]++;
a[a[0]] = k;
int temp, i = a[0];
while (i>1) {
if (a[i]>a[i/2]) {
temp = a[i];
a[i] = a[i/2];
a[i/2] = temp;
}
i /= 2;
}
}
printf("Inserimento in maxHeap eseguito con successo!\n");
}
void insertKeyInMaxHeapStruct (int k, heap *h) {
if (h->dim == 0) {
h->a = malloc (2*sizeof(int));
h->a[1] = k;
h->dim++;
printf("La struct che mi hai passato è vuota.\nInserisco la radice..\n");
}
else {
h->a = realloc (h->a, (h->dim+2)*sizeof(int));
h->dim++;
h->a[h->dim] = k;
int temp, i = h->dim;
while (i>1) {
if (h->a[i]>h->a[i/2]) {
temp = h->a[i];
h->a[i] = h->a[i/2];
h->a[i/2] = temp;
}
i /= 2;
}
}
printf("Inserimento in maxHeapStruct eseguito con successo!\n");
}
void insertKeyInMinHeap (int k, int *a) {
if (a[0] == 0) {
a = realloc (a, 2*sizeof(int));
a[0]++;
a[a[0]] = k;
printf("L'array che mi hai passato è vuoto.\nInserisco la radice..\n");
}
else {
a = realloc (a, (a[0]+2)*sizeof(int));
a[0]++;
a[a[0]] = k;
int temp, i = a[0];
while (i>1) {
if (a[i]<a[i/2]) {
temp = a[i];
a[i] = a[i/2];
a[i/2] = temp;
}
i /= 2;
}
}
printf("Inserimento in maxHeap eseguito con successo!\n");
}
void insertKeyInMinHeapStruct (int k, heap *h) {
if (h->dim == 0) {
h->a = malloc (2*sizeof(int));
h->a[1] = k;
h->dim++;
printf("La struct che mi hai passato è vuota.\nInserisco la radice..\n");
}
else {
h->a = realloc (h->a, (h->dim+2)*sizeof(int));
h->dim++;
h->a[h->dim] = k;
int temp, i = h->dim;
while (i>1) {
if (h->a[i]<h->a[i/2]) {
temp = h->a[i];
h->a[i] = h->a[i/2];
h->a[i/2] = temp;
}
i /= 2;
}
}
printf("Inserimento in minHeapStruct eseguito con successo!\n");
}
int extractKeyFromMaxHeapAndGetPosition (int k, int *a) {
if (a[0] != 0) {
int i, temp;
_Bool trovato = 0;
for (i = 1; i<=a[0] && !trovato; i++)
if (a[i] == k) {
temp = a[i];
a[i] = a[a[0]];
a[a[0]] = temp;
a[0]--;
trovato = 1;
maxHeapify(a);
}
if (trovato) {
printf("L'elemento %d è stato estratto con successo dall'array!!\n", k);
return i-1;
}
printf("L'elemento %d non appartiene all'array!!\n", k);
}
else {
printf("L'array che mi hai passato è vuoto, non posso estrarre!!\n");
return -1;
}
}
int extractKeyFromMaxHeapStructAndGetPosition (int k, heap *h) {
if (h->dim != 0) {
int i, temp;
_Bool trovato = 0;
for (i = 1; i<=h->dim && !trovato; i++)
if (h->a[i] == k) {
temp = h->a[i];
h->a[i] = h->a[h->dim];
h->a[h->dim] = temp;
h->dim--;
trovato = 1;
maxHeapifyStruct(h);
}
if (trovato) {
printf("L'elemento %d è stato estratto con successo dalla struct!!\n", k);
return i-1;
}
printf("L'elemento %d non appartiene alla struct!!\n", k);
}
else {
printf("La struct che mi hai passato è vuota, non posso estrarre!!\n");
return -1;
}
}
int extractKeyFromMinHeapAndGetPosition (int k, int *a) {
if (a[0] != 0) {
int i, temp;
_Bool trovato = 0;
for (i = 1; i<=a[0] && !trovato; i++)
if (a[i] == k) {
temp = a[i];
a[i] = a[a[0]];
a[a[0]] = temp;
a[0]--;
trovato = 1;
minHeapify(a);
}
if (trovato) {
printf("L'elemento %d è stato estratto con successo dall'array!!\n", k);
return i-1;
}
printf("L'elemento %d non appartiene all'array!!\n", k);
}
else {
printf("L'array che mi hai passato è vuoto, non posso estrarre!!\n");
return -1;
}
}
int extractKeyFromMinHeapStructAndGetPosition (int k, heap *h) {
if (h->dim != 0) {
int i, temp;
_Bool trovato = 0;
for (i = 1; i<=h->dim && !trovato; i++)
if (h->a[i] == k) {
temp = h->a[i];
h->a[i] = h->a[h->dim];
h->a[h->dim] = temp;
h->dim--;
trovato = 1;
minHeapifyStruct(h);
}
if (trovato) {
printf("L'elemento %d è stato estratto con successo dalla struct!!\n", k);
return i-1;
}
printf("L'elemento %d non appartiene alla struct!!\n", k);
}
else {
printf("La struct che mi hai passato è vuota, non posso estrarre!!\n");
return -1;
}
}
int main(int argc, char** argv) {
int *a = malloc(1*sizeof(int));
inizializzaArray(a);
insertKeyInMaxHeap(20, a);
insertKeyInMaxHeap(11, a);
insertKeyInMaxHeap(0, a);
insertKeyInMaxHeap(320, a);
insertKeyInMaxHeap(67, a);
insertKeyInMaxHeap(18, a);
insertKeyInMaxHeap(45, a);
stampArray(a);
int t = extractKeyFromMaxHeapAndGetPosition(45, a);
stampArray(a);
printf("La posizione di 45 era: %d\n", t);
heap h;
inizializzaArrayStruct(&h);
insertKeyInMaxHeapStruct(20, &h);
insertKeyInMaxHeapStruct(11, &h);
insertKeyInMaxHeapStruct(0, &h);
insertKeyInMaxHeapStruct(320, &h);
insertKeyInMaxHeapStruct(67, &h);
insertKeyInMaxHeapStruct(18, &h);
insertKeyInMaxHeapStruct(45, &h);
stampArrayStruct(&h);
int s = extractKeyFromMaxHeapStructAndGetPosition(45, &h);
stampArrayStruct(&h);
printf("La posizione di 45 era: %d\n", s);
return (EXIT_SUCCESS);
}
Tags: C Program MaxHeap and MinHeap, max heap and min heap example, max heap and min heap in data structure, convert max heap to min heap, max heap sort program in c, build max heap program in c, max heap program in c++, min heap program in c, min and max heap tree code for c++.
Learn More :
C Program
- Using Bash to input stuff into c program
- Difficult C Programming Questions
- Write a c program to find largest among three numbers using binary minus operator three numbers using binary minus operator
- PRINTING ASCII VALUE USING C PROGRAM
- MULTIPLICATION OF TWO MATRICES USING C PROGRAM
- FIND OUT SUM OF DIAGONAL ELEMENTS OF A MATRIX USING
- Write A C Program To Find Out Transport Of A Matrix
- Factorial of 100 in C Program
- Multiplication of large numbers in c
- Division of Large Numbers in C Program
- BINARY SEARCH USING C PROGRAM
- BINARY SEARCH THROUGH RECURSION USING C PROGRAM
- FIND FACTORIAL OF A NUMBER USING RECURSION IN C PROGRAM
- FIND GCD OF A NUMBER USING RECURSION IN C PROGRAM
- FIND SUM OF DIGITS OF A NUMBER USING RECURSION USING C PROGRAM
- FIND POWER OF A NUMBER USING RECURSION USING C PROGRAM
- REVERSE A NUMBER USING RECURSION IN C PROGRAM
- SWAP TWO VARIABLES WITHOUT USING THIRD USING C PROGRAM VARIABLE
- Write A C Program For Swapping Of Two Arrays
- SWAPPING OF STRINGS USING C PROGRAM
- CONVERSION FROM DECIMAL TO OCTAL USING C PROGRAM
- CONVERSION FROM DECIMAL TO OCTAL USING C PROGRAM
- CONVERSION OF DECIMAL TO BINARY USING C PROGRAM
- CONVERSION OF FAHRENHEIT TO CENTIGRADE USING C PROGRAM
- C or C++ Program To Find Bonus Amount