Heap

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em ciência da computação, um heap é uma estrutura de dados organizada como árvore binária balanceada, seguindo algumas regras. Este pode ser implementado em um arranjo, para que ele seja acessado como uma árvore binária, usando as seguintes operações[1] [2] :

PAI(i)
   return i/2
 
ESQUERDA(i)
   return i*2
 
DIREITA(i)
   return i*2 + 1
Um arranjo acessado como uma arvore binaria balanceada.[1]

Se estiver bem implementado estas são macros ou procedimentos "inline".[2] Estas operações podem ser executadas rapidamente usando operações bit a bit.[2] Para o filho esquerdo desloca os bits a esquerda, para o direito desloca os bits para a esquerda e aplica a operação "ou" com 1.[2] Para encontrar o pai, desloca um bit a direita.[2] A vantagem de usar operações bit a bit, é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.[2]

Características[editar | editar código-fonte]

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.[1]

Operações[editar | editar código-fonte]

As operações mais comuns em heaps são:

Inserção[editar | editar código-fonte]

  • Inserção: Adicionar um novo nó ao heap..

Codigo em Java

public void insertItem(Object k, Object e) throws InvalidKeyException {
    if(!comp.isComparable(k))
        throw new InvalidKeyException("Invalid Key");
    Position z = T.add(new Item(k, e));
    Position u;
    while(!T.isRoot(z)) { // bubbling-up
        u = T.parent(z);
        if(comp.isLessThanOrEqualTo(key(u),key(z)))
             break;
        T.swapElements(u, z);
        z = u;
     }
}

Remoção[editar | editar código-fonte]

  • Remoção: Remove o elemento da raiz do heap.

Codigo em Java

public Object removeMin() throws PriorityQueueEmptyException {
    if(isEmpty())
        throw new PriorityQueueEmptyException("Priority Queue Empty!");
    Object min = element(T.root());
    if(size() == 1)
        T.remove();
    else {
        T.replaceElement(T.root(), T.remove());
        Position r = T.root();
        while(T.isInternal(T.leftChild(r))) {
            Position s;
            if(T.isExternal(T.rightChild(r)) || comp.isLessThanOrEqualTo(key(T.leftChild(r)),key(T.rightChild(r))))
                s = T.leftChild(r);
            else
                s = T.rightChild(r);
            if(comp.isLessThan(key(s), key(r))) {
                T.swapElements(r, s);
                r = s;
            }
            else
                break;
        }
    }
}
  • Merge (união): Juntar dois heaps para formar um novo heap com todos os elementos de ambos.

Implementações[editar | editar código-fonte]

Heaps podem ser implementados para fornecer o menor valor (heaps de mínimo) ou o maior valor (heaps de máximo). Nesse quesito, as implementações podem variar. Outra variação comum está no index do elemento raiz (o menor elemento do heap, se for um heap de mínimo, ou o maior, se for um heap de máximo): enquanto algumas implementações optam por usar o index 0 do array como raiz, outras optam por usar o index 1. Essa variação altera as operações de obter os filhos a partir do pai, e de obter o pai a partir de um dos filhos.

Implementação em C++[editar | editar código-fonte]

// Implementação de MinHeap em C++ por Rafael Perrella
// Quanto à mistura de idiomas, os métodos privados estão em português apenas para facilitar o entendimento...
 
template<class T>
class BinaryMinHeap
{
	// Usamos um vector<T>, em vez de um T* heap, para não termos que nos preocupar com alocação de memória
	vector<T> heap;
 
	inline int filhoE(int i) { return i<<1; } // (i<<1) é similar a (i*2)
	inline int filhoD(int i) { return (i<<1)|1; } // ((i<<1)|1) é similar a ((i*2)+1)
	inline int pai(int i) { return i>>1; } // (i>>1) é similar a (i/2)
 
	void corrigeSubindo(int index)
	{
		// Enquanto o valor do filho for menor do que o valor do pai, troca o pai com o filho e sobe
		for (; index > 1 && heap[index] < heap[pai(index)]; index = pai(index))
			swap(heap[index], heap[pai(index)]);
	}
 
	void corrigeDescendo(int index=1) // também conhecida como heapify(index)
	{
		// Repete enquanto index ainda tiver filho
		while (filhoE(index) < heap.size())
		{
			// Seleciona o filho com menor valor (esquerda ou direita?)
			int filho = filhoE(index);
			if (filhoD(index) < heap.size() && heap[filhoD(index)] < heap[filhoE(index)])
				filho = filhoD(index);
 
			// Se o valor do pai é menor do que o valor do menor filho, terminamos
			if (heap[index] < heap[filho])
				break;
 
			// Caso contrário, trocamos o pai com o filho no heap e corrigimos agora para o filho
			swap(heap[index], heap[filho]);
			index = filho;
		}
	}
 
public:
	BinaryMinHeap() { T nil; heap.push_back(nil); }
	inline T& top() { return heap[1]; }
	inline int size() { return heap.size() - 1; }
	inline bool empty() { return heap.size() <= 1; }
 
	void push(T v)
	{
		heap.push_back(v);
		corrigeSubindo(size());
	}
 
	void pop()
	{
		if (heap.size() > 1)
		{
			swap(heap[1], heap.back());
			heap.pop_back();
			corrigeDescendo();
		}
	}
 
	void buildHeap(vector<T>& array)
	{
		// Copia o array recebido para o array do heap
		T nil;
		heap.clear();
		heap.push_back(nil);
		for (int i = 0; i < array.size(); i++)
			heap.push_back(array[i]);
 
		// Constrói o heap
		for (int index = size()/2; index; index--)
			corrigeDescendo(index);
	}
};

Os métodos mais importantes na implementação são o corrigeSubindo e o corrigeDescendo. O primeiro corrige o heap para um determinado índice recém-adicionado. É utilizado na inserção, pois para inserir um elemento em um heap podemos simplesmente adicioná-lo no final do array, e depois empurrá-lo para cima na árvore enquanto ele for menor que o pai (ou maior, se for um heap de máximo). Já o corrigeDescendo realiza o mesmo processo, mas é utilizado quando o elemento precisa ser empurrado para baixo, e não para cima. Isso acontece na remoção, pois nesta operação selecionamos o último elemento do array e trocamos com a raiz. Assim, podemos descartar a raiz (que está no final do array agora, bastando remover o último elemento do array). Porém, o último elemento do array (que foi movido para a raiz) provavelmente não é o menor, e a raiz deve sempre guardar o menor elemento. Portanto, devemos empurrar o elemento para baixo até que o heap esteja corrigido. Segue uma implementação recursiva dessas duas funções:

	void corrigeSubindo(int index)
	{
		// Se index não é a raiz e o valor do index for menor do que o valor de seu pai,
		// troca seus valores (index e pai(index)) e corrige para o pai
		if (index > 1 && heap[index] < heap[pai(index)])
		{
			swap(heap[index], heap[pai(index)]);
			corrigeSubindo(pai(index));
		}
	}
 
	void corrigeDescendo(int index=1)
	{
		// Se index tem filho
		if (filhoE(index) < heap.size())
		{
			// Seleciona o filho com menor valor (esquerda ou direita?)
			int filho = filhoE(index);
			if (filhoD(index) < heap.size() && heap[filhoD(index)] < heap[filhoE(index)])
				filho = filhoD(index);
 
			// Se o valor do pai é menor do que o valor do menor filho, terminamos
			if (heap[index] < heap[filho])
				return;
 
			// Caso contrário, trocamos o pai com o filho no heap e corrigimos agora para o filho
			swap(heap[index], heap[filho]);
			corrigeDescendo(filho);
		}
	}

Utilização[editar | editar código-fonte]

Uma das utilizações mais tradicionais do heap é no algoritmo de ordenação heapsort, que utiliza a propriedade do heap de o maior (ou menor valor) localizar-se na raiz do mesmo e fazer a ordenação dos dados de uma maneira bastante eficiente.

Também 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.

Referências

  1. a b c Cormen(2001), p. 127.
  2. a b c d e f Cormen(2001), p. 128.

Ver também[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

  • Cormen, T.H. ET AL. Introduction to algorithms. [S.l.]: The MIT press, 2001.