6

Quando a ordenação é feita com o heapsort e os candidatos para a raíz da árvore forem iguais, a ordem de prioridade é dada para o elemento de maior ou menor índice no vetor original ou é dada pela posição que estes elementos ocupam na árvore (prioridade para o lado esquerdo pelo menor índice)?

1 Resposta 1

4

Pelo que eu entendi, a pergunta se refere à primeira parte do algoritmo, que é a construção do heap.

Como as implementações tradicionais do heapsort (siftDown) utilizam uma estrutura de árvore armazenada em um array, conforme o exemplo abaixo:

Dada a ávore inicial armazenada em um array:

v = { 1, 9a, 9b, 3, 4, 5, 6 }

A estrutura da ávore é:

      .. 1 ..
     /       \
    /         \
   9a         9b
  /  \       /  \
 /    \     /    \
3      4   5      6

Os elementos iguais (9), aqui, são representados como 9a e 9b.

E conforme um exemplo de implementação em linguagem C, extraído da Wikipedia em:
Wikipedia - Heapsort - Código em C

void heapsort(int a[], int n) {

   int i = n / 2, pai, filho, t;

   for (;;) {
      if (i > 0) {
          i--;
          t = a[i];
      } else {
          n--;
          if (n == 0) return;
          t = a[n];
          a[n] = a[0];
      }

      pai = i;

      //Primeiro será feita a comparação com o filho da esquerda.
      filho = i * 2 + 1;

      while (filho < n) {

         // Se o filho da esquerda for menor do que o filho da direita,
         // então será feita a troca do filho que será comparado.
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              filho++;
          if (a[filho] > t) {
             a[pai] = a[filho];
             pai = filho;
             filho = pai * 2 + 1;
          } else {
             break;
          }
      }
      a[pai] = t;
   }
}

No momento da escolha entre os candidatos iguais, quem vai para a raíz é o 9a (filho esquerdo), pois na comparação:

a[filho + 1] > a[filho]

o valor (no vetor), indexado pela variável filho (9a "no lado esquerdo") é igual ao valor armazenado no índice filho+1 (9b "no lado direito"), portanto, o índice filho não é incrementado (na linha filho++).

O comentário no código também confirma que a comparação sempre é feita a partir do lado esquerdo da árvore:

//Primeiro será feita a comparação com o filho da esquerda.

Minha conclusão, a partir das premissas:

  • análise do algoritmo (eu não testei)
  • a pergunta se refere apenas a fase de construção do heap
  • a forma como a ávore é armazenada no array

é que a resposta correta é:

a prioridade é dada pela posição que estes elementos ocupam na árvore (prioridade para o lado esquerdo pelo menor índice)


Referências utilizadas para elaborar a resposta:

KNUTH, Donald Ervin. The Art of Computer Programming: v.3 - Sorting and Searching. 2nd Edition. Westford (MA): Addison-Wesley Professional, 2012. 782 p (Volumes 1-4A Boxed Set)
ISBN-13:978-0321751041
Páginas consultadas: 144 a 148

PRESS, William et al. Numerical Recipes in C: The Art of Scientific Computing. 2nd Edition. New York (NY): Cambridge University Press, 1992. 994 p (reimpresso em 2002 e corrigido para o software versão 2.10)
ISBN-13: 978-0521431088
Páginas consultadas: 336 a 338

ATALLAH, Mikhail J. et al. Algorithms and Theory of Computation Handbook.1st Edition. Boca Raton (FL):CRC Press, 1312 p (Chapman & Hall/CRC Applied Algorithms and Data Structures series (Book 1))
ISBN-13: 978-0849326493
Páginas consultadas: 3-7 e 3-8


Links complementares, para referência online:

Wikipedia - Heapsort

Wikipedia - Ordenação estável

Wikipedia - Heapsort - em inglês - o texto está mais completo e tem um "passo-a-passo" do algoritmo)

Wikipedia - Heap

LANG, HANS WERNER - Heapsort

Sorting Algorithm Animations - Heap Sort

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .