Heap

Heap é uma estrutura de dados que serve para agilizar o acesso a um elemento que tem prioridade em relação a outros, como por exemplo, um maior ou menor elemento entre vários.
Com um Heap, somos capazes de ter acesso ao maior elemento (por exemplo) em O(1).
• O Heap também é conhecido como fila de prioridade e possui implementação pré-definida em várias linguagens de programação;
• Sua estrutura pode ser visualizada como uma árvore binária completa;
• Apesar de ser visualizado como uma árvore, o Heap é construído sobre um array H.
• O número de elementos inseridos nele é salvo num atributo size.

A principal característica de um Heap é a relação entre o pai e seus filhos. Num Heap de máximo, por exemplo, o pai é sempre maior que seus filhos. Num Heap de mínimo, o pai é sempre menor que os filhos. Usualmente chamamos MaxHeap e MinHeap.

Podemos escrevê-lo assim:

struct Heap{
    int H[10];
    int size;
}

Como o Heap é visto na forma de árvore, podemos deduzir que cada elemento vai ter dois filhos (à esquerda e à direita). 
Mas como representar esses filhos no array?
Simples, para cada elemento na posição $i$, seus filhos vão estar na posição $2i$ e $2i + 1$.
Analogamente, o pai de $i$ é $i/2$.
É perceptível que essas fórmulas não funcionam se a raiz da árvore for a posição 0 do array, pois 2*0 = 0, logo o 0 seria o pais de si mesmo, e isso não é verdade.
Se a raiz for a posição 1, temos 2*1 = 2 e 2*1+1 = 3, e de fato é isso que queremos:


Se o fato da raiz ser o índice 1 do array for um incômodo, é possível utilizar a posição 0 e utilizar as fórmulas $2i + 1$ e $2i + 2$, mas é recomendável usar a raiz como a posição 1, em breve explicarei o motivo.

Vamos tratar do MinHeap.

INSERÇÃO

Vamos supor que o Heap esteja vazio (ou seja, size = 0).

Sempre que adicionamos um elemento no Heap, colocamos o mesmo na primeira posição livre do array (ou seja, na posição size + 1).

Como o Heap está vazio, adicionamos na primeira posição size + 1 = 0 + 1 = 1 e acrescentamos 1 ao size.

Suponha um Heap formado pela inserção consecutiva dos elementos {1,4,7,8,3}.

inserindo: 1
H: 1

inserindo: 4
H: 1 4

inserindo: 7
H: 1 4 7

inserindo: 8
H: 1 4 7 8

inserindo: 3
H: 1 4 7 8 3

Podemos reparar, no entanto, que só adicionando assim, não mantemos a propriedade do MinHeap do pai ser menor que os filhos, pois o 4 é maior que o 3 e ainda assim é seu pai.

Quando adicionamos, devemos então subir o elemento até seu lugar correto.

Esse método é chamado BubbleUp:
  
Podemos ver que até o 8, nenhum elemento quebrava a propriedade do MinHeap, mas o 3 quebra, então subimos até sua posição correta, trocando ele por seu pai enquanto ele for maior que seu pai.


Essa foi fácil, mas vejamos num Heap maior.

Considerando as inserções consecutivas {2,3,4,5,6,7,8,1}


Podemos ver que o 1 quebra a propriedade do MinHeap, então subimos ele até sua posição ideal (enquanto ele for maior que seu pai):


Como o Heap vai sempre estar certo, assim que um elemento que quebre a propriedade for adicionado, quando ele chegar na sua posição ideal, o Heap inteiro vai continuar certo.
Podemos implementar o add com BubbleUp assim:

struct Heap{
    int H[10];
    int size;
    #define INF 0x3f3f3f3f

    //construtor poe um numero muito pequeno
    //na posicao 0 para que ele nunca seja
    //trocado e sirva como limite para o
    //BubbleUp parar de subir os elementos    
    Heap(){size = 0; H[0] = -INF;}

    //operator overload em [] para acessar
    //diretamente os elementos de H
    int& operator[] (int i) {return H[i];}
    
    //add insere o elemento na primeira
    //posicao livre e da BubbleUp nele
    void add(int v){
        H[size + 1] = v;
        BubbleUp(++size);
    }
    
    void BubbleUp(int pos){
        int pai = pos >> 1;          //pos>>1 é pos/2 de maneira rápida
        while(H[pos] < H[pai]){      //enquanto o filho for menor que o pai
            swap(H[pos], H[pai]);    //troca eles
            pos = pai;               //atualiza posição do filho
            pai>>=1;                 //atualiza posição do pai para o novo pai
        }
    }
};


int main(){
    Heap h;
    h.add(2); h.add(3); h.add(4); h.add(5); 
    h.add(6); h.add(7); h.add(8); h.add(1);

    for(int i = 1; i <= h.size; i++){
        printf("%d ", h[i]);
    }
}

A saída desse programa gera um array que, ao ser representado como árvore, fica igual à árvore mais acima.
O & no int& significa que estamos passando o elemento propriamente dito e não uma cópia dele. Se não tivéssemos o &, o método retornaria uma cópia do int H[i].

Como o Heap é uma árvore completa e, no pior caso, o novo elemento vai subir até o topo da árvore, a complexidade da inserção equivale à altura da árvore, ou seja: 

 Complexidade da Inserção: O(lg(n))  

BUSCA (E REMOÇÃO)

O Heap, na prática, não é uma estrutura com objetivo de procurar alguém no interior do array. Ele serve fundamentalmente para acessar o valor com maior prioridade, em O(1).
Remover um elemento do Heap significa tirar o primeiro elemento do array, que é a raiz e consequentemente, o elemento de maior prioridade.
Dito isso, dado que tiramos o primeiro elemento, o que acontece com o Heap?
Ele não pode ficar sem raiz, então o que devemos fazer?

A solução é simples, basta tirar o último elemento do array e jogar ele na posição da raiz.

No entanto, se fizermos isso, a nova raiz vai quebrar a propriedade do Heap. O que devemos fazer então?

Devemos descer com ele até sua posição certa (como ele estava na última posição, ele tinha um valor grande, logo ele deve descer até que seja novamente maior que seu pai).

Esse método se chama Heapify.

Vamos supor o MinHeap formado pelos elementos {1,2,3,4,5,6,7}
A árvore é assim:


Se aplicarmos o remover, o que acontece é:
• Guardamos o valor de maior prioridade, isto é, o 1
• Jogamos o último elemento do Heap (o 7) no lugar do primeiro (o 1)
• Aplicamos um Heapify no 7 para corrigir sua posição
• Retornamos o valor de maior prioridade

Assim ocorre o Heapify:


É visível que, quando fazemos isso, o próximo elemento de maior prioridade vai subir para o seu lugar devido.

Podemos implementar assim:

struct Heap{
    int H[10];
    int size;
    //define INF 0x3f3f3f3f

    Heap(){size = 0; H[0] = -INF;}

    int& operator[] (int i) {return H[i];}

    int del(){
        int n = H[1];               //salva elemento de maior prioridade
        H[1] = H[size--];           //joga o último elemento no início
        Heapify(1);                 //desce esse elemento até sua posição ideal
        return n;
    }

    void Heapify(int pos){
        int left = pos<<1;          //pos * 2 é o filho da esquerda
        int right = pos<<1|1;       //pos * 2 + 1 é o filho da direita
        int menor = pos;            //variável para guardar o menor elemento

        if(left <= size && H[left] < H[menor]) menor = left;
        if(right <= size && H[right] < H[menor]) menor = right;
        if(menor != pos){           //se mudou, significa que um dos filhos era menor
            swap(H[pos], H[menor]); //troca o pai pelo filho
            Heapify(menor);         //chamada recursiva para continuar descendo
        }
    }
};

int main(){
    Heap h;
    for(int i = 1; i < 10; i++) h[i] = ++h.size;

    for(int i = 1; i <= h.size; i++) printf("%d ", h[i]); pf("\n");
    printf("Elemento de maior prioridade: %d\n", h.del());
    for(int i = 1; i <= h.size; i++) printf("%d ", h[i]); pf("\n");
    printf("Elemento de maior prioridade: %d\n", h.del());
    for(int i = 1; i <= h.size; i++) printf("%d ", h[i]); pf("\n");
}

A complexidade dessa remoção é o tempo de um Heapify, isto é:

 Complexidade da Remoção: O(lg(n))  

HEAPSORT

Quando removemos um elemento do Heap, ele garantidamente é o de maior prioridade (no caso, o maior ou menor elemento entre todos).

Após a remoção, o maior elemento entre todos os que sobraram ocupa o local do anterior.

Se o removermos também, o mesmo acontece, então se removermos elemento por elemento até que o tamanho do Heap seja 0, é notável que os elementos vão saindo em ordem de prioridade (crescente ou decrescente), e com isso, temos uma ordenação.

Eis um exemplo simples de um HeapSort (usando as funções já implementadas):

int main(){
    Heap h;
    for(int i = 9; i > 0; i--) h.add(i);
    while(h.size) printf("%d ", h.del());
}

Como o HeapSort remove todos os n elementos, e para cada remoção, faz um Heapify, de custo $lg(n)$, o custo total de um HeapSort é:

 Complexidade do HeapSort: O(n lg(n))  

CONSTRUÇÃO DO HEAP

Existem duas abordagens para se construir o Heap, são elas:

Top-Down

A abordagem Top-Down se dá quando construímos o Heap a partir da inserção sucessiva de elementos, ou seja, para cada elemento e, colocamos ele na primeira posição livre do array e fazemos um BubbleUp para subi-lo até a posição ideal.
Para um Heap de n elementos, fazemos n inserções, com um BubbleUp que leva lg(n) no pior caso, então a complexidade do Top-Down é:

 Complexidade do Top-Down: O(n lg(n))  

Bottom-Up

A abordagem Bottom-Up é diferente. Dado que temos um array já preenchido, transformamos ele num Heap usando essa abordagem. 
Para fazer isso, fazemos uso de um método comumente chamado de BuildHeap, que é bem simples:
Para cada posição i do array partindo do meio até o início, fazemos um Heapify em i.

Não é tão intuitivo o motivo pelo qual isso funciona... vejamos:


A razão é:
- Como ele começa pelo meio do array, ele vai começar pelo penúltimo nível mais baixo.
Prova: o primeiro nível tem $2^1$ elementos, o segundo, $2^2$, o k-ésimo, $2^k$.
Cada nível é equivalente à soma de todos os anteriores mais 1, logo o último nível é a soma de todos os anteriores mais 1.
Se temos n nós, supondo que temos x nós no último nível, então:
$x + (x-1) = n$
$2x - 1 = n$
$x = \frac{n}{2} - \frac{1}{2}$    que arredondamos para $\frac{n}{2}$ por conveniência.
Então, podemos dizer que a metade do array é o alicerce entre o último nível e o penúltimo.

- Como começamos do penúltimo nível e vamos voltando nível por nível, e como o Heapify desce um maior e sobe um menor, garantidamente todos os elementos podem subir todos os níveis.
Se, por exemplo, o elemento de maior prioridade começa no último nível, quando começarmos a fazer o Heapify no penúltimo nível, ele vai poder subir um nível. Quando fizermos no antepenúltimo nível, ele (que agora está no penúltimo nível) vai subir novamente, e assim em diante. Isso se dá para todos os elementos, e por isso o BuildHeap funciona.

struct Heap{
    int H[10];
    int size;
    #define INF 0x3f3f3f3f

    Heap(){size = 0; H[0] = -INF;}

    int& operator[] (int i) {return H[i];}

    void Heapify(int pos){
        int left = pos<<1;
        int right = pos<<1|1; 
        int menor = pos; 

        if(left <= size && H[left] < H[menor]) menor = left;
        if(right <= size && H[right] < H[menor]) menor = right;
        if(menor != pos){ 
            swap(H[pos], H[menor]); 
            Heapify(menor); 
        }
    }

    void BuildHeap(){
        for(int i = size>>1; i > 0; i--) //size>>1 = size/2 

            Heapify(i); 
    }
};

int main(){
    Heap h;
    for(int i = 9; i > 0; i--) h[++h.size] = i;

    printf("Heap antes: \t");
    for(int i = 1; i < h.size; i++) printf("%d ", h[i]);
    printf("\n");

    h.BuildHeap();

    printf("Heap depois: \t");
    for(int i = 1; i < h.size; i++) printf("%d ", h[i]);
    printf("\n");
}

Qual a complexidade disso?
Simples, como aplicamos Heapify, que roda em $lg(n)$ em $\frac{n}{2}$ elementos, o tempo obviamente é $O(\frac{n}{2} * lg(n)) = O(n*lg(n))$, certo?
ERRADO. O tempo do BuildHeap é limitado superiormente por n, ou seja, ele é $O(n)$ no pior caso. Mas por que? Com um pouco de matemática, podemos provar isso.

Para cada um dos $\frac{n}{2}$ elementos em que aplicamos Heapify, eles não vão descer a altura toda de fato, por exemplo, os elementos do penúltimo nível vão descer, no máximo, um nível. O número de operações que um BuildHeap faz está diretamente relacionado à altura do Heap. 

Podemos definir a altura máxima que os elementos vão descer assim:
Se o Heap tem n elementos:
- No último nível temos (arredondando) $\frac{n}{2}$ elementos, que vão descer no máximo 0 de altura (pois não podem descer mais).
- No penúltimo nível, temos $\frac{n}{4}$ elementos, que vão descer no máximo 1 de altura.
- ...
- No primeiro nível, temos 1 elemento, que vai descer no máximo $lg(n)$ de altura.

Formalmente, o número total de operações pode ser definido como:
$$\sum_{i = 0}^{lg(n)} i \frac{n}{2^i}$$   onde: 

$i$ é a altura que estamos levando em conta (variando de 0 até $lg(n)$)
$\dfrac{n}{2^i}$ é o número de elementos na altura $i$ (considerando as folhas com altura 0)

Como $i$ $\dfrac{n}{2^{i}} = 0$ para $i$ $ = 0 $, podemos começar o somatório em $i = 1$ (e teremos exatamente as operações totais do BuildHeap):

$$\sum_{i = 1}^{lg(n)} i\frac{n}{2^i} \quad = \quad n \sum_{i = 1}^{lg(n)} \frac{i}{2^i}  $$

Olhando apenas para o somatório, não é trivial chegar a um valor exato, mas podemos usar o seguinte artifício:
$$\sum_{i = 1}^{lg(n)} \frac{i}{2^i} \quad < \quad \sum_{i = 1}^{\infty} \frac{i}{2^i}  $$

Vamos chamar o lado direito da desigualdade de $S_1$, que pode ser representado assim:

$$S_1  = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + ... $$

Calculamos $2 * S_1$:
$$2S_1  = 1 + \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + ... $$

Note que apenas dividimos o denominador de todos os termos por 2.
Se fizermos a diferença entre $2S_1$ e $S_1$ (subtraindo apenas os termos de mesmo denominador), temos:

$$2S_1 - S_1 = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... $$
$$2S_1 - S_1 - 1= \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... $$

Vamos chamar o lado direito da última igualdade de $S_2$:

$$S_2 = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... $$

Podemos calcular $S_2$ assim:
$$2S_2 = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... $$
$$2S_2 = 1 + S_2$$
$$S_2 = 1$$

Conseguimos calcular $S_2$, vamos usá-lo em $S_1$:

$$2S_1 - S_1 - 1= S_2 $$ $$S_1 - 1= 1 $$ $$S_1 = 2 $$

Conseguimos calcular $S_1$, logo, podemos dizer que:

$$\sum_{i = 1}^{lg(n)} \frac{i}{2^i} \quad < \quad \sum_{i = 1}^{\infty} \frac{i}{2^i}  $$
$$\sum_{i = 1}^{lg(n)} \frac{i}{2^i} \quad < \quad S_1  $$
$$\sum_{i = 1}^{lg(n)} \frac{i}{2^i} \quad < \quad 2 $$

Então, para estimar número total de operações, basta multiplicar os dois lados por $n$:
$$n \sum_{i = 1}^{lg(n)} \frac{i}{2^i} \quad < \quad 2n $$
Ou seja, no pior caso, a complexidade é limitada superiormente por 2n.

 Complexidade do Bottom-Up: O(n)  

Em C++, o MaxHeap já tem implementação pronta, o priority_queue (é possível alterar para MinHeap).
Existem ainda outros tipos de Heap, em especial o Heap de Fibonacci, que realiza inserções em tempo O(1).