6
When ordination is done with the heapsort and the candidates for the tree root are equal, the priority order is given to the highest or lowest index element in the vector original or is given by the position these elements occupy in the tree (priority to the left by the lowest index)?
4
From what I understand, the question refers to the first part of the algorithm, which is the construction of the heap.
Like the traditional implementations of heapsort (siftDown) use a tree structure stored in an array, as the example below:
Given the initial tree stored in an array:
v = { 1, 9a, 9b, 3, 4, 5, 6 }
The structure of the tree is:
.. 1 ..
/ \
/ \
9a 9b
/ \ / \
/ \ / \
3 4 5 6
The same elements (9), here are represented as 9a and 9b.
And as an example of implementation in C language, extracted from Wikipedia in:
Wikipedia - Heapsort - Code in 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;
}
}
At the time of choosing between equal candidates, who goes to the root is the 9a (left child), because in the comparison:
a[filho + 1] > a[filho]
the value (in the vector), indexed by the variable filho (9a "on the left side") is equal the value stored in the index filho+1 (9b "on the right side"), therefore, the child index is not incremented (on the line filho++).
The comment in the code also confirms that the comparison is always made from the left side of the tree:
//Primeiro será feita a comparação com o filho da esquerda.
My conclusion, from the premises:
is that the correct answer is:
the priority is given by the position these elements occupy in the tree (priority to the left side by the lowest index)
References used to prepare the response:
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 Sep)
ISBN-13:978-0321751041
Pages consulted: 144 to 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 (reprinted in 2002 and corrected for software version 2.10)
ISBN-13: 978-0521431088
Pages consulted: 336 to 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
Pages consulted: 3-7 and 3-8
Complementary links for online reference:
Wikipedia - Heapsort - in English - the text is more complete and has a "step-by-step" algorithm)
Browser other questions tagged classification
You are not signed in. Login or sign up in order to post.