#include <stdio.h>

#include <stdlib.h>



void heapAdjust(int *queue, int len, int start)

{

	int p = start;

	int left = (p+1)*2 - 1;

	int right = (p+1)*2;

	int min = 0;

	int tmp;

	while( left <= len-1 ){

		if(right <= len-1){

			if(queue[left] < queue[right]){

				min = left;	

			}else{

				min = right;

			}

		}else{

			min = left;

		}

		if(queue[min] < queue[p]){

			tmp = queue[p];

			queue[p] = queue[min];

			queue[min] = tmp;	

		}



		p = min;

		left = (p+1)*2 - 1;

		right = (p+1)*2;

	}	

}



void heapSort(int *seq, int len)

{

	int i,j;

	int queue[100];

	for(i=0; i<len; i++){

		queue[i] = seq[i];

	}



	for( i=len/2-1; i>=0; i--){

		heapAdjust(queue, len, i);

	}



	j = 0;

	for( i=len-1; i>=0; i--){

		seq[j++] = queue[0];

		queue[0] = queue[i];

		heapAdjust(queue, i+1, 0);

	}

}

		

void main()

{

	int ancient[] = {49,38,65,97,76,13,27,49};

	int seq[] = {49,38,65,97,76,13,27,49};

	int n = sizeof(seq)/sizeof(int);

	int i;



	printf("Simple selection sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	heapSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");



}