Listas de Prioridade

Operações Básica

Seleção: Fornece o elemento de maior prioridade
Inserção: Insere um elemento na lista
Remoção: Remove o elemento de maior prioridade
Alteração: Altera a prioridade de um elemento
Construção: Inserir todos os elementos a partir de uma estrutura vazia.

 

Implementação	Seleção	Inser.	Rem.	Alter.	Constr.
Lista Não Ordenada (DE)	O(n)	O(1)	O(n)	O(n)	O(n)
Lista Ordenada (Ordenação Total)	O(1)	O(n)	O(1)	O(n)	O(nlogn)
Heap (Ordenação Parcial)	O(1)	O(logn)	O(logn)	O(logn)	O(n)

Heap

Árvore binária completa que obedece as seguintes propriedades:
 
• Se nó x é pai de nó y então chave(x) > chave(y)
• No último nível da árvore as folhas ``são colocadas'' em seqüência, da esquerda para direita.


Um heap pode ser implementado utilizando-se um vetor, V, e obedecendo-se a seguinte propriedade:

• V[i] < = V{i/2] , para 1 < i < = n   (Onde n é o total de elementos no heap e cada elemento do vetor representa uma chave).

Algorítmos de Inserção e Remoção

// Aumentando a prioridade de um elemento void Subir(Filho)  {       Pai = piso( Filho / 2 )      if( Pai >= 1 )      {           if( V[Filho] > V[Pai] )           {                 Troca V[Filho] e V[Pai]                 Subir(Pai)           }      } }	// Diminuindo a prioridade de um elemento void Descer(Pai,Total) {     Filho = 2*Pai   // Filho Esquerdo     if( Filho <= Total)     {          if( Filho < Total) // Tem FilhoDir          {                if(V[Filho+1] > V[Filho])  ++Filho          }          if( V[Pai] < V[Filho])           {                Trocar Pai e Filho                 Descer(Filho,Total)          }      } }
void Inserir(chave) {    V[n+1] = chave // n é a ultima posição do vetor    ++n     Subir(n) }	void Remover() {    V[1] = V[n]    --n    Descer(1,n) }

Construção de um Heap a partir de um vetor 'qualquer'

Algorítmo I [ O(nlogn) ]	Algorítmo II [ O(n) ]
for(i=2;i<=n;++i) Subir(i)	for(i=piso(n/2);i>=1;--i) Descer(i,n)

Intuição para diferença na Complexidade:

• Existem mais nó nos niveis mais baixos da árvore do que nos mais altos

(Nível 1 tem 1 nó, a raiz, enquanto o nível m tem 2^(m-1) nós).
• O algorítmo I tem que subir nós que estão nos níveis mais baixos. (mais caminhos longos)

Por exemplo, todos os pais de folhas terão que subir até a raiz (no pior caso).
• O algorítmo II tem que descer nós que estão nos níveis mais baixos. (mais caminhos curtos)

Por exemplo,  todos os pais de folhas terão que descer apenas 1 nó (no pior caso).

Obs: Estou considerando o nível 1 (da raiz) como sendo o mais alto da árvore.

Heap Sort

Entrada: Vetor V de tamanho n, com n elementos 'fora de ordem'
Saida: Vetor V ordenado.
Complexidade Pior Caso: O(nlogn)

void HeapSort(V,n)
{
   Construir Heap usando Algorítmo II
   m = n
   while( m > 1)
   {
       V[1] <=> V[m]
       m = m - 1
       Descer(1,m)
   }
}

Material de Apoio