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
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 - em inglês - o texto está mais completo e tem um "passo-a-passo" do algoritmo)