O que diabos é um “heap”?

É comum que o desenvolvedor em linguagens como C chame a área de alocação dinâmica da memória de “heap”. Segundo Donald E. Knuth em seu The Art of Computer Programming, Volume I, a área de alocação dinâmica começou a ser chamada de heap por alguns autores à partir de 1975. O motivo é linguístico: Um “heap”, no inglês coloquial, é somente um conjunto desordenado de itens, numa gaveta, por exemplo… Nesse sentido, a área de alocação dinâmica é tudo menos um “heap”. Não é à toa que em C++ essa área é chamada de free store ou “armazenamento livre”, relegando o termo tradicional ao esquecimento.

Mas o fato permanece… Essa área continua, tradicionalmente, sendo chamada de “heap”.

O que diabos é um heap, afinal de contas? É uma estrutura baseada em árvore binária com características especiais. Nessa estrutura, todo nó pai tem uma chave “maior” que as chaves dos nós filhos, como mostrado na figura abaixo:

Eis um heap!

Essa estrutura permite a implementação, por exemplo, de uma “fila de prioridades”, e permite a estruturação da árvore num simples array… Cada nível da árvore é colocado em posições específicas do array… Por exemplo, esse heap da figura pode ser codificado como:

int heap[] = {
  100, 19, 36, 17, 3, 25, 1, 2, 7
};

Aqui, heap[0] sempre conterá a chave do nó raiz. Os dois nós que seguem, heap[1] e heap[2], são os nós filhos do raiz. Os nós heap[3] e heap[4] são filhos de heap[1], da mesma forma, heap[5] e heap[6] são filhos de heap[2]. E é lógico que as duas últimas posições são filhos da posição 3.

As duas próximas posições, que faltam no array, seriam então filhas da posição 4. Se quiséssemos inserir uma chave “4” ela entraria logo depois da chave 7 (o último item do array), tornando-se filha da posição da chave “3”, o que viola o heap. Teríamos que fazer um swap dessas posições para manter a estrutura correta. Note: Inserir novos itens é colocá-los no final da lista, mas é necessário que o array seja percorrido e reordenado… Se um nó filho for maior que o nó pai (do nó raiz aos nós folhas) temos que trocá-los de lugar (experimente inserir, ao invés de “4” uma chave “40”).

Ao percorrer a árvore teremos sempre os nós folha com as menores chaves e podemos usar isso como um critério de prioridade para “desenfileirar” os nós a partir da mais alta prioridade, que estará sempre no nó raiz, desde que reordenemos os nós filhos. No caso da árvore da figura anterior, depois de retirarmos o item 100, o item 19 passa a ser o nó raiz:

De novo, tivemos que reordenar os nós para que o heap continue válido. Basta percorrer cada nó, verificando se existe um filho com chave maior. Se houver, faz a troca. A rotina de reordenação é bem simples:

#define swap(a,b) { int t; t = (a); (a) = (b); (b) = t; }

/* Rotina NÂO otimizada. Dá pra melhorar um cadinho,
   deixo como exercício pra você! */
void sort_heap(int *p, size_t size)
{
  size_t i, j;

  for (i = 0; i < size - 1; i++)
  {
    j = 2*i+1;

    if (j < size)
      if (p[i] < p[j])
        swap(p[i], p[j]);

    if (++j < size)
      if (p[i] < p[j])
        swap(p[i], p[j]);
  }
}

Obviamente, se quiséssemos poderíamos alterar a lógica colocando os nós com chaves menores como pais das chaves maiores, tornando o nó raiz o portador da menor chave, sempre…

Inserimos o novo item no final do array e retiramos do começo. O que constitui uma fila (queue), mas os itens inseridos serão ordenados, com base na chave de seu nó pai… Ao retirar, do início da fila, retiraremos o item com a chave de maior valor… O que caracteriza uma fila de prioridade!