Code:
#include <stdio.h>
#include <stdlib.h>
#define LEFT(x) (2*x) /* left child of a node */
#define RIGHT(x) ((2*x)+1) /* right child of a node */
#define PARENT(x) (x/2) /* parent of a node */
#define SWAP(tmp,x,y) tmp = x ; x = y ; y = tmp /* swap to variables */
void max_heapify(int A[], int i, int size) {
int l, r, largest, temp;
l = LEFT(i);
r = RIGHT(i);
if(l <= size && A[l-1] > A[i-1])
largest = l;
else largest = i;
if(r <= size && A[r-1] > A[largest-1])
largest = r;
if(largest != i) {
SWAP(temp, A[i-1], A[largest-1]);
max_heapify(A, largest, size);
}
}
void build_max_heap(int A[], int size) {
int i;
for(i = (size/2); i>0; i--)
max_heapify(A, i, size);
}
int heap_maximum(int A[]) {
return A[0];
}
int heap_extract_max(int A[], int *size) {
int max;
if(*size < 1) {
printf("Heap underflow.\n");
return -1;
}
max = A[0];
A[0] = A[(*size)-1];
*size = (*size)-1;
max_heapify(A, 1, *size);
return max;
}
void heap_increase_key(int A[], int i, int key) {
int temp;
if(key<A[i]) {
printf("New key is smaller than current key.\n");
return;
}
A[i] = key;
while(i > 0 && A[PARENT(i)] < A[i]) {
SWAP(temp, A[i], A[PARENT(i)]);
i = PARENT(i);
}
}
void max_heap_insert(int A[], int *size, int max_size, int key) {
if(*size >= max_size) {
printf("Heap capacity exceeded, new element not added.\n");
return;
}
*size = (*size)+1;
A[*size]=-1; /*should be - infinity*/
heap_increase_key(A, *size, key);
}
int main(int argc, char *argv[]) {
int maxsize, size, i;
int *array;
maxsize=size=5;
i=0;
array = malloc(maxsize*sizeof(int));
while(i<maxsize) {
array[i]=-1;
i++;
}
array[0]=0;
array[4]=7;
array[3]=3;
build_max_heap(array, size);
for(i=0; i< size; i++)
printf("%i ", array[i]);
printf("\n");
heap_extract_max(array, &size);
for(i=0; i< size; i++)
printf("%i ", array[i]);
printf("\n");
max_heap_insert(array, &size, maxsize, 2);
for(i=0; i< size; i++)
printf("%i ", array[i]);
printf("\n");
heap_extract_max(array, &size);
for(i=0; i< size; i++)
printf("%i ", array[i]);
printf("\n");
max_heap_insert(array, &size, maxsize, 10);
for(i=0; i< size; i++)
printf("%i ", array[i]);
printf("\n");
free(array);
return 0;
}