Um heap é uma estrutura de dados organizada como árvore binária, seguindo algumas regras.

Características

Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.

A árvore binária do heap deve estar completa até pelo menos seu penúltimo nível e, se o seu último nível não estiver completo, todos os nós do último nível deverão estar agrupados à esquerda.

Estrutura em C/C++:

//Autor: Filipe Areias Névola
//Ano: 2007
//Licensa: Você pode usar e alterar, mas deve manter o Autor
//Representando um Heap como vetor
//Filho esquerdo: 2*i+1
//Filho direito: 2*i+2
//Pai: piso(i/2)
struct tHeap{
    int *v,n,tam;
};

Operações em C/C++:
Inserção

bool insercao(tHeap &h,int x){
    if(h.tam==h.n)
        return true;
    h.n++;
    h.v[h.n]=x;
    subida(h,h.n);
    return true;
}

void subida(tHeap &h, int i){
    if(i>1)
        if(h.v[i]>h.v[i/2]){
            troca(h.v[i],h.v[i/2]);
            subida(h,floor(i/2));
        }
}

Remoção

bool remocao(tHeap &h,int &x){
    if(h.n==0)
        return true;
    x=h.v[1];
    h.v[1]=h.v[h.n];
    h.n--;
    descida(h,1);
    return true;
}

void descida(tHeap &h, int i){
    int aux;
    if(h.n>=2*i){
        if(h.n>=2*i+2){
            if(h.v[2*i+1]>h.v[2*i+2])
                aux=2*i+1;
            else
                aux=2*i+2;
        }else
            aux=2*i+1;
        if(h.v[i]<h.v[aux]){
            troca(h.v[i],h.v[aux]);
            descida(h,aux);
        }
    }
}

Utilização

Pode ser usada como heaps de prioridades onde a raíz é a maior prioridade. Com relação ao vetor a, inserção e remoção, é da ordem O(log(n)).

Outra utilização de heaps são em algoritmos de seleção. Operações de encontrar o maior, ou menor, elemento de um conjunto de números é realizado de uma forma bastante eficiente, em comparação com a utilização de uma lista ligada ordenada.

Fontes: Teoria Wikipédia e Implementações Filipe Névola