#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    double *A;
    int length;
    int size;
} theap;


int parent(int i);
int left(int i);
int right(int i);

void max_heapify(theap h, int i);
void build_max_heap(theap h);

void print_spaces(int n);


void print_spaces(int n)
{
    int j;
    for (j = 0; j < n; j++) printf(" ");
}

void print_heap(theap h)
{
    int 
	i, j, n = h.length,
	levels = 1 + (int) log2((double) n),
	gap = 1 << levels;
    printf("gap: %d", gap);
    print_spaces(4 * (gap / 2) - 2);
    for (i = 1; i <= n; i++) {
	if (floor(log2(i)) == log2(i)) {
	    printf("\n");
	    gap = gap >> 1;
	    print_spaces(4 * (gap / 2) - 2);
	}
	printf("%4g", h.A[i]);
	print_spaces(4 * gap - 4);
    }
    printf("\n\n");
}


int main(int argc, char *argv[]) {
    int i, n;
    theap h;
    if (argc != 2) {
	printf("\nUsage: %s <n>\n\n", argv[0]);
	return 1;
    }
    n = atoi(argv[1]);
    srandom(time(NULL));
    h.A = (double*) malloc((n+1) * sizeof(double));
    h.length = n;
    for (i = 1; i <= n; i++) {
	h.A[i] = 1.0 * random() / RAND_MAX;
	h.A[i] = floor(100 * h.A[i]);
    }
    print_heap(h);
    build_max_heap(h);
    print_heap(h);
    printf("\n");
    return 0;
}
    


int parent(int i) {
    return i >> 1;
}
int left(int i) {
    return i << 1;
}
int right(int i) {
    return 1 + (i << 1);
}


void max_heapify(theap h, int i) {
    double tmp;
    int l = left(i), r = right(i), largest = i;
    if (l <= h.size && h.A[l] > h.A[i]) largest = l;
    if (r <= h.size && h.A[r] > h.A[largest]) largest = r;
    if (largest != i) {
	tmp = h.A[i];
	h.A[i] = h.A[largest];
	h.A[largest] = tmp;
	max_heapify(h, largest);
    } 
    return;
}

void build_max_heap(theap h) {
    int i;
    h.size = h.length;
    for (i = parent(h.length); i >= 1; i--) {
	max_heapify(h, i);
    }
}