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++.