#include "common.h"
#include <stdio.h>

/* NOTA: Estamos usando aqui uma variável SA, que basicamente é A deslocado em
 * uma posição. Para que isso?! Para poder usar indices mais parecidos com os de * pascal nos vetores e com isso fazer com que fique mais conveniente trabalhar
 * com a HEAP. Em especial &SA[1] == &A[0].
 *
 * Baseado em http://www.yendor.com/programming/sort/
 */


/* Algumas funções para auxiliares */
inline int PAI	    (int i) { return i >> 1 ;}
inline int DIREITA  (int i) { return i<<1; }
inline int ESQUERDA (int i) { return DIREITA(i) + 1;}

void desce(int SA[], int n, int no)
{
	int menor;
	int l;
	int r;

	l = ESQUERDA(no);
	r = DIREITA(no);

	COUNT_COMP;
	if ((l <= n) && ( SA[l] < SA[no] )) {
		menor=l;
	} else {
		menor = no;
	};
	
	COUNT_COMP;
	if ((r <= n ) && (SA[r] < SA[menor])) {
		menor = r;
	};
	
	COUNT_COMP;
	if (menor != no) {
		swap(&SA[menor], &SA[no]);
		desce(SA,n,menor);
	};
	
}

void build_heap (int SA[], int n)
{
	int i=0;
	for (i = PAI(n); i > 0; i-- ){
		desce(SA,n, i);
	}
}

void partial_heap_sort( int A[], int n, int k)
{
	int i, heap_size;
	int *SA = A - 1;

	build_heap(SA,n);

	/* Coloca os k primeiros elementos no final*/
	heap_size=n;
	for (i = 0; i < k ; i++) {
		swap(&SA[n - i], &SA[1]);
		heap_size--;
		desce(SA, heap_size ,1);
	}
	
	/* Coloca os k primeiros elementos no começo*/
	for (i = 0; i < k ; i++) {
		swap(&SA[n - i], &SA[1 + i]);
	}
	
}