Lesson10

Amontoados binários

O amontoado binário, ou binary heap, é uma árvore (quase) completa em que nenhum nó tem uma chave superior à raiz e a chave de cada nó é sempre maior ou igual que as chaves de ambos os filhos, i.e., max-heap. Se invertermos a propriedade, ou seja, se a chave de cada nó é sempre menor ou igual que as chaves de ambos os filhos, passamos a ter um min-heap em vez de um max-heap. A árvore diz-se quase completa uma vez que todos os níveis estão completos excepto, eventualmente, o último nível. O último nível está no entanto sempre preenchido da esquerda para a direita.

Exercício: Qual dos seguintes vectores corresponde a um max-heap?

1. {50, 25, 30, 27, 24, 21, 28}
2. {50, 30, 25, 27, 24, 28, 21}
3. {60, 50, 9, 40, 41, 10, 8}
4. {40, 15, 18, 13, 11, 14, 16}
5. {60, 30, 80, 10, 35, 70, 40}

O elementos de um vector podem também ser vistos como um amontoado binário (neste caso min-heap):

Fonte: Wikipedia

No caso de um vector de dimensão $n$, indexado em $0\leq i < n$, temos que:

• o pai do nó $i$ é o nó $\lfloor (i+1)/2\rfloor - 1$;
• os filhos do nó $i$ são os nós $2i$ e $2(i+1)$.

Estas operações são normalmente implementadas como:

#define LEFT(x)   (((x) << 1) + 1)
#define RIGHT(x)  (((x) + 1) << 1)
#define PARENT(x) ((((x) + 1) >> 1) - 1)

Operações típicas sobre amontoados (max-heap):

• fixUp
• fixDown
• buildHeap

fixUp

Permite corrigir o amontoado quando a chave de um elemento é aumentada, caso em que o nó pode ter de ser deslocado para cima.

Implementação:

void fixUp(Item a[], int k)
{
  while (k > 0 && less(a[PARENT(k)], a[k])) {
    exch(a[k], a[PARENT(k)]); 
    k = PARENT(k);
  }
}

fixDown

Permite corrigir o amontoado quando a chave de um elemento é diminuída.

Dado um nó a cujo elemento associado é diminuída a chave:

• esta operação confirma se ambos os filhos são menores do que elemento;
• se não for o caso, troca o elemento com o filho maior e procede de forma recursiva com o nó onde o filho maior estava.

void fixDown(Item a[], int l, int r, int k)
{
  int ileft, iright, largest=k;

  ileft=l+LEFT(k-l);
  iright=l+RIGHT(k-l);

  if (ileft<=r && less(a[largest],a[ileft])) 
    largest=ileft;
  if (iright<=r && less(a[largest],a[iright]))
    largest=iright;

  if (largest!=k){
    exch(a[k],a[largest]);
    fixDown(a, l, r, largest);
  }
}

buildHeap

Transforma um vector arbitrário com $N$ elementos num amontoado:

• efectua fixDown até todos os elementos cumprirem a condição do amontoado;
• uma das formas de o fazer é aplicar o fixDown ao pai com o índice $k$ mais elevado, i.e., $k=N/2-1$, e a todos os índices $i<k$.

Implementação:

void buildheap(Item a[], int l, int r){
  int k, heapsize = r-l+1;
  for (k = heapsize/2-1; k >= l; k--)
    fixDown(a, l, r, l+k);
}

Problema

Como utilizar estas operações para implementar uma fila com prioridade?

Heap sort

Dado um vector arbitrário, o algoritmo Heap sort opera da seguinte forma:

1. transforma o vector num amontoado;
2. troca o primeiro elemento (raiz) com o último;
3. reduz a dimensão do amontoado em uma unidade;
4. aplica o fixDown sobre a nova raiz para reparar o amontoado;
5. repete a partir do passo 2 enquanto a dimensão do amontoado for superior a 1.

Implementação:

void heapsort(Item a[], int l, int r) { 
  buildheap(a,l,r);
  while (r-l > 0) {
    exch(a[l], a[r]);
    fixDown(a, l, --r, l);
  }
}

Animação, pelo Prof. David Galles, CS Dept, Univ of San Francisco.

Exercício: Ilustre a operação do Heap sort sobre o vector $A=\{5,13,2,25,7,17,20,8,4\}$.
Solução:

  A -> | 5|13| 2|25| 7|17|20| 8| 4|
               +--------+--+
  A -> | 5|13|20|25| 7|17| 2| 8| 4|
            +-----+--+
  A -> | 5|25|20|13| 7|17| 2| 8| 4|
                  +-----------+--+
  A -> | 5|25|20|13| 7|17| 2| 8| 4|
         +--+--+
  A -> |25| 5|20|13| 7|17| 2| 8| 4|
            +-----+--+
  A -> |25|13|20| 5| 7|17| 2| 8| 4|
                  +-----------+--+
  A -> |25|13|20| 8| 7|17| 2| 5| 4|

  A -> | 4|13|20| 8| 7|17| 2| 5|   25
         +--+--+
  A -> |20|13| 4| 8| 7|17| 2| 5|   25
               +--------+--+
  A -> |20|13|17| 8| 7| 4| 2| 5|   25

  A -> | 5|13|17| 8| 7| 4| 2|   20 < 25
         +--+--+
  A -> |17|13| 5| 8| 7| 4| 2|   20 < 25  
               +--------+--+
  A -> |17|13| 5| 8| 7| 4| 2|   20 < 25

  A -> | 2|13| 5| 8| 7| 4|   17 < 20 < 25
         +--+--+
  A -> |13| 2| 5| 8| 7| 4|   17 < 20 < 25
            +-----+--+
  A -> |13| 8| 5| 2| 7| 4|   17 < 20 < 25

  A -> | 4| 8| 5| 2| 7|   13 < 17 < 20 < 25
         +--+--+
  A -> | 8| 4| 5| 2| 7|   13 < 17 < 20 < 25
            +-----+--+
  A -> | 8| 7| 5| 2| 4|   13 < 17 < 20 < 25

  A -> | 4| 7| 5| 2|   8 < 13 < 17 < 20 < 25
         +--+--+
  A -> | 7| 4| 5| 2|   8 < 13 < 17 < 20 < 25
            +-----+
  A -> | 7| 4| 5| 2|   8 < 13 < 17 < 20 < 25

  A -> | 2| 4| 5|   7 < 8 < 13 < 17 < 20 < 25
         +--+--+
  A -> | 5| 4| 2|   7 < 8 < 13 < 17 < 20 < 25

  A -> | 2| 4|   5 < 7 < 8 < 13 < 17 < 20 < 25
         +--+
  A -> | 4| 2|   5 < 7 < 8 < 13 < 17 < 20 < 25

  A -> | 2|   4 < 5 < 7 < 8 < 13 < 17 < 20 < 25

  A -> 2 <  4 < 5 < 7 < 8 < 13 < 17 < 20 < 25

Exercício: Considere que se pretende ordenar o vector em baixo, utilizando o algoritmo de ordenação Heap sort. Qual será a configuração do vector após a extração do segundo elemento?

int a[] = {10, 2, 17, 14, -1, 4, 8, 0, 7};

O Heap sort não é estável!

Complexidade

Em primeiro lugar analizar-se-á o fixDown. Seja $i$ um nó da árvore e suponha-se que $n$ é o número de nós abaixo do nó $i$. Duas observações importantes: existem inteiros não negativos $k$ e $r$ tais que $r<2^{k+1}$ e $n=\sum_{j=0}^k2^{j}+r$; dadas as duas árvores de descendentes do nó $i$, o número de nós da árvore da esquerda é sempre maior ou igual ao número de nós da árvore da direita. Seja $m$ o descendente de $i$ à esquerda, o número de nós abaixo de $m$ é dado por $\sum_{j=0}^{k-1} 2^{j}+r'$ em que $r'=\min(r,2^k)$. Dado que $$ \frac{\sum_{j=0}^{k-1} 2^{j}+r'}{n}= \frac{\sum_{j=0}^{k-1} 2^{j}+r'}{\sum_{j=0}^k2^{j}+r}\leq \frac{\sum_{j=0}^{k-1} 2^{j}+2^k}{\sum_{j=0}^k2^{j}+2^k}= \frac{2^{k+1}-1}{2^{k+1}-1+2^k}= \frac{2\ 2^k-1}{3\ 2^k-1} \stackrel{\scriptscriptstyle k\to\infty}{\displaystyle \longrightarrow} \frac{2}{3}, $$ tem-se que o número de nós em cada uma das árvores descendentes de $i$ é menor ou igual a $\frac{2}{3}n$. Logo, têm-se os seguintes tempos de execução para o fixDown:

void fixDown(int *a, int s, int i){             /*    O(1)    */
  int l = LEFT(i), r = RIGHT(i), m = i, x = 0;  /*    O(1)    */
  if(l <= s && a[l-1] > a[i-1]) m = l;          /*    O(1)    */
  if(r <= s && a[r-1] > a[m-1]) m = r;          /*    O(1)    */
  if(m != i){                                   /*    O(1)    */
    x = a[i-1];                                 /*    O(1)    */
    a[i-1] = a[m-1];                            /*    O(1)    */
    a[m-1] = x;                                 /*    O(1)    */
    fixDown(a,s,m);}}                           /* <= T(2n/3) */

Portanto $T_{fixDown}(n) \leq T_{fixDown}(2n/3) + O(1)$ e, tomando $a=1$, $b=3/2$ e $f(n)=\sum_ic_i$, pelo segundo caso do Teorema Mestre, tem-se que $T_{fixDown}(n) = O(\log n)$.

Considere-se agora o caso do buildHeap. Sabe-se que a altura máxima de uma árvore é dada por $\lfloor \log_2 s \rfloor$, em que $s$ é número de elementos na árvore. Nota-se que, se a altura do $i$-ésimo elemento for $h_i$, o tempo do fixDown aplicado ao $i$-ésimo elemento é $O(h_i)$. Por outro lado, se o número de elementos da árvore for $s$, tem-se que o número de elementos $N(h)$ à altura $h$ é dado por $\lceil s/2^{h+1}\rceil$. Portanto, obtêm-se os seguintes tempos para o buildHeap:

void buildHeap(int *a, int s){                  /*    O(1)    */
  int i = 0;                                    /*    O(1)    */
  for(i = s>>1; i > 0; i--)                     /*    O(s)    */
    fixDown(a,s,i);}                            /* s/2^{h+1} O(h), sum over 0 < h < log_2(s) */

Ou seja, o tempo de execução do buildHeap é dado por:

$T_{buildHeap}(s)$
$\quad = O(1)+O(s)+\sum_{h=0}^{\lfloor \log_2 s\rfloor}\lceil s/2^{h+1}\rceil O(h)$
$\quad \leq O(1)+O(s)+O(s \sum_{h=0}^{\infty}h/2^{h+1})$
$\quad = O(1)+O(s)+O(s \sum_{h=0}^{\infty}h(\frac{1}{2})^{h+1})$
$\quad = O(1)+O(s)+O(\frac{s}{4} \sum_{h=0}^{\infty}h(\frac{1}{2})^{h-1})$
$\quad = O(1)+O(s)+O(\frac{s}{4} ((\lambda x. \frac{\partial}{\partial x} \sum_{h=0}^{\infty}x^h)\ \ \frac{1}{2}))$
$\quad = O(1)+O(s)+O(\frac{s}{4} ((\lambda x. \frac{\partial}{\partial x} \frac{1}{1-x})\ \ \frac{1}{2}))$
$\quad = O(1)+O(s)+O(\frac{s}{4} ((\lambda x. \frac{1}{(1-x)^2})\ \ \frac{1}{2}))$
$\quad = O(1)+O(s)+O(\frac{s}{4} 4)$
$\quad = O(s)$

Finalmente têm-se os seguintes tempos para o heapsort:

void heapsort(int *a, int s){                           
  int i = 0, x = 0;                             /*    O(1)    */
  buildHeap(a,s);                               /*    O(s)    */
  for(i = s; i>1; i--){                         /*    O(s)    */
    x = a[i-1];                                 /*    O(s)    */
    a[i-1] = a[0];                              /*    O(s)    */
    a[0] = x;                                   /*    O(s)    */
    fixDown(a,i-1,1);}}                         /* s O(log s) */

Ou seja, $T_{heapsort}(s)=O(1)+O(s)+ O(s \log s)= O(s \log s)$.

Avaliação experimental

Ordenação por comparação

Algumas considerações a respeito dos algoritmos de ordenação estudados até aqui, todos eles baseados em comparações entre elementos. O limite inferior para qualquer algoritmo de ordenação baseado em comparações é $\Omega(N\log N)$. Se pensarmos que para $N$ chaves existem $N!$ permutações diferentes, em que qualquer uma delas pode ser a entrada de um algoritmo de ordenação, e se representarmos as comparações (e trocas) que um algoritmo tem de fazer sobre essa entrada até ordenar as $N$ chaves, obtemos uma árvore com $N!$ folhas. Dado que uma árvore com $N$ folhas tem de ter uma altura necessariamente superior ou igual a $log(N!) \sim N\log N$, temos que para pelo menos uma das entradas, qualquer algoritmo de ordenação vai realizar pelo menos $N\log N$ passos.

Podemos no entanto obter algoritmos mais eficientes desde que os mesmos não sejam baseados em comparações. Podemos por exemplo utilizar informação relativa às chaves utilizadas, como vamos ver na próxima aula.