Contato

  • Jean Paulo Martins (jeanmartins utfpr edu br)
  • Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

Introdução

Para compreendermos o significado e a utilidade de filas de prioridade, vamos utilizar como referência inicial o algoritmo de ordenação selection sort. Esse algoritmo de ordenação funciona de forma bastante intuitiva

  • A cada passo, selecione o menor elemento e o insira na posição adequada.

Se assumirmos que o objetivo seja ordenar a sequência de forma crescente, o menor elemento deve ser inserido na parte inicial da sequência. Na primeira iteração, portanto, o menor elemento de toda a sequência será identificado e inserido na posição zero. Na segunda iteração, o próximo menor elemento será identificado e inserido na posição um, até que toda a sequência esteja ordenada.

Podemos perceber que em todo o procedimento acima descrito, a etapa principal é a identificação do menor elemento da sequência. Uma forma simples de implementarmos essa ideia seria uma função min, que retorna o índice do menor elemento num intervalo de $i$ a $f$.

int min(int* v, int i, int f) {
    int menor = i++;
    for (; i < f; i++)
        if (v[i] < v[menor]) menor = i;
    return menor;
}

Utilizando a função min, o algoritmo de ordenação selection sort se torna bastante simples.

void selectsort(int* v, int n) {
    for (int i = 0; i < n; i++)
        swap(v, i, min(v, i, n));
}

Observemos que a repetição do laço for em selectsort acontece $n$ vezes. Em cada uma dessas vezes, a função min é chamada para identificar o menor elemento. Na primeira chamada, min tem que percorrer toda a sequência para identificar o menor elemento, ou seja $n-1$ comparações. Na segunda chamada, min terá que percorrer um elemento a menos, pois o primeiro já foi identificado, ou seja, $n-2$ comparações.

Para contabilizarmos todas as etapas efetuadas por min, basta somar o número de comparações feito em cada uma delas.

Filas de prioridades

A análise simples do selection sort, nos indica claramente que o maior processamento feito por este algoritmo ocorre durante a identificação do menor elemento da sequência. Sendo o custo de min determinante para o custo total do algoritmo. Em cada iteração, o único objetivo é identificar o elemento mínimo, o que nos leva a uma pergunta.

  • Não haveria uma estrutura de dados que nos permitisse sempre obter o menor elemento de forma mais rápida do que a feita por min?

Uma das respostas para essa pergunta são as filas de prioridades. Tais estruturas tem como principal objetivo organizar os dados de modo que obter o mínimo/máximo elemento seja tão rápido quanto possível. Diferentemente das filas comuns, em que a ordem de inserção de um elemento determina sua ordem de remoção, nas filas de prioridade é a prioridade que determina a ordem de saída de um elemento. A prioridade, no caso mais simples é o próprio valor do elemento.

void selectsort(int* v, int n) {
    for (int i = n - 1; i > 0; i--)
        swap(v, i, max(v, 0, i + 1));
}

Heap