Estrutura de dados que suporta as operações de:

 - inserção de um elemento junto de uma chave de prioridade em tempo O(log n)
 
 - remoção de um elemento com maior (ou menor, mas não ambos) chave de prioridade em tempo O(log n)

Construir um heap a partir de n elementos pode ser feito em tempo linear

Também é possível implementar operação que remove ou atualiza a chave de elementos específicos do meio do heap



Ideia baseada em árvore binária:

 - vamos considerar a versão do heap de máximo
 
    - uma árvore binária é um heap de máximo se todo nó é >= que os seus filhos
 
 - vamos exemplificar com os valores de 1 a 6
 
    - Inserir o 7
	
	   - coloca na próxima posição e sobe até encontrar pai maior ou igual que o elemento
	   
	- Remover o topo
	
	   - pega o último, coloca no topo e desce sempre pelo lado do filho maior, até ambos os filhos serem menores ou iguais ao pai
	   
 - Poderíamos implementar esta estrutura usando uma árvore binária com registro para células com apontadores para filhos esquerdo e direto e para o pai
 
 - No entanto, como esta árvore conceitual é completa ou quase-completa, podemos implementá-la num vetor 
 
    - usamos a convenção de que o vetor começa na posição 1 e termina na posição n
 
int filhoEsq (int p) {
	return 2*p;
}

int filhoDir (int p) {
	return 2*p + 1;
}

int pai (int f) {
	return f/2; // note que o resultado da divisão corresponde ao piso da divisão por 2
}

void sobeHeap(int v[], int k) {
	int f, p;
	f = k;
	while (f>1 && v[p = pai(f)] < v[f]) {
		troca(v, f, p);	
		f = p;
	}
}

Invariante:

 - no início de cada iteração a relação v[i] <= v[pai(i)] = v[i/2] vale para todo i em 1..n diferente de f
 
    - conseguimos mostrar que ao sair do laço a propriedade do heap está reestabelecia para todos os elementos


Eficiência:

 - como f é dividido por 2 a cada iteração o algoritmo executa no máximo lg(n) iterações
 
    - note que log_2 n = lg n corresponde ao número de vezes que podemos dividir um número por 2 antes que o resultado seja <= a 1


 
void insereHeap(int x, inv v[], int *n) {
	int f;
	*n=*n+1;
	f = *n;
	v[f] = x;

	sobeHeap(v, f);
}



void desceHeap(int v[], int n, int k) {
	int p = k, fe, fd, f;
	
	fe = filhoEsq(p);
	fd = filhoDir(p);
	
	while (fe <= n) {
		if (fd <= n && v[fd] > v[fe])
			f = fd;
		else f = fe;
		if (v[p] >= v[f]) break;
		troca(v, f, p);
		p = f;
		fe = filhoEsq(p);
		fd = filhoDir(p);
	}
}

Invariante:

 - no início de cada iteração v[i] <= v[pai(i)] = v[i/2] vale para todo i em 1..n exceto para fe e fd
 
    - conseguimos mostrar que ao sair do laço a propriedade do heap está reestabelecia para todos os elementos


Eficiência:

 - como p é multiplicado por 2 a cada iteração o algoritmo executa no máximo lg n iterações
 
    - note que o laço termina antes que p se torne > n. Depois de lg n iterações temos p = k*2^(lg n) = k*n >= n, já que k>=1. Portanto, o número de iterações não passa de lg n.



int removeHeap (int v[], int *n) {
	int ret = v[1];
	v[1] = v[*n];
	*n = *n - 1;
	
	desceHeap(v, *n, 1);
	
	return ret;
}



// função que constrói um heap a partir de um vetor em tempo linear
void heapify(int v[], int n) {
	int i;
	
	for (i = n/2; i >= 1; i--)
		desceHeap(v, n, i);
}

Quão eficiente é essa operação?

Primeiro, vamos lembrar que

\sum_i=1^n 1/2^i = 1/2 + 1/4 + 1/8 + ... + 1/2^n <= 1 

Note que o desceHeap realiza 0 operações por elemento da última metade do vetor, 
1 operação por elemento do quarto seguinte, 2 operações por elemento do oitavo seguinte, 
e assim por diante, até realizar lg n operações para o elemento da raíz (i=1).

Escrevendo isso em linguagem matemática, temos

0*n/2 + 1*n/4 + 2*n/8 + ... + (lg n - 1) * n/(2^lg n) = 
1*n/2^2 + 2*n/2^3 + 3*n/2^4 + ... + (lg n - 1) * 1 = 
\sum_i=1^(lg n - 1) i*n/2^(i+1) = 
n * \sum_i=1^(lg n - 1) i/2^(i+1) = 
n * \sum_i=1^(lg n - 1) \sum_j=1^i 1/2^(i+1) = 
n * \sum_j=1^(lg n - 1) \sum_i=j^(lg n - 1) 1/2^(i+1) = 
n * \sum_j=1^(lg n - 1) 1/2^j \sum_i=j^(lg n - 1) 1/2^(i+1-j) = 
k = i + 1 - j => se i = j então k = j + 1 - j = 1 e se i = lg n - 1 então k = lg n - j
n * \sum_j=1^(lg n - 1) 1/2^j \sum_k=1^(lg n - j) 1/2^k <=
n * \sum_j=1^(lg n - 1) 1/2^j * 1 <= 
n * 1 * 1 <= n