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

/* Max-heap implementation and heapsort */

#define ARRAYSIZE 20
typedef struct {
	int A[ARRAYSIZE];
	int heaplimit; 
} Heap;



#define HEAP_LEFT(n) (2*(n+1) -1  )
#define HEAP_RIGHT(n) (2*(n+1) )
#define HEAP_PARENT(n) (n/2)
#define SWAP( a, b ) { int tmp; tmp = a; a = b; b = tmp; }

void heapify ( Heap *h, int pos ) {
	int l = HEAP_LEFT( pos );
	int r = HEAP_RIGHT( pos );
	int largest;
	largest = pos;
	if (l <= h->heaplimit && h->A[l] > h->A[pos]) {
		largest = l;
	} 
	if (r <= h->heaplimit && h->A[r] > h->A[largest]) {
		largest = r;
	}

	if (largest != pos) {
		SWAP( h->A[largest], h->A[pos] );
		heapify( h, largest );
	}
}

void print_array( Heap *h ) {
	int i;
	for (i=0; i < ARRAYSIZE; i++)
		printf( "%d ", h->A[i] );
	printf( "\n" );
}


void build_heap( Heap *h ) {
	h->heaplimit = ARRAYSIZE -1;

	int i;

	for (i = h->heaplimit/2; i >=0; i--){
		heapify( h, i );
	}
}

void my_heapsort( Heap *h ) { /* heapsort clashes with stdlib-defined func */
	build_heap( h );
	int i;

	for (i=ARRAYSIZE-1; i >= 0; i--) {
		SWAP( h->A[0] /* Max element */, h->A[h->heaplimit] );
		h->heaplimit--;
		heapify( h, 0 );
	}

}
int main( void ) {
	
	Heap H;

	
	int i;
	for (i=0; i < ARRAYSIZE; i++)
		H.A[i] = random() % 1000;
	
	my_heapsort( &H );
	print_array( &H );

	return 0;
}