Sorting with heapsort

Question

Sorting with heapsort

Navigation

#1 by (4 votes)

6

When ordering with heapsort and the candidates for the root of the tree are equal , the order of priority is given to the element of higher or lower index in the original vector or is it given by the position that these elements occupy in the tree (priority to the left by the lowest index)?

asked by anonymous 26.01.2016 / 15:51

1 answer

Return data as JSON using ASP.NET MVC SQL Query Optimization in MySQL and Index

score 4 · Accepted Answer

As I understand it, the question refers to the first part of the algorithm, which is the construction of heap .

As the traditional implementations of heapsort ( siftDown ) use a tree structure stored in an array, as in 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 equal elements ( 9 ) here are represented as 9a and 9b .

And as an example of implementation in C language, extracted from Wikipedia at:
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 moment of choosing between the equal candidates, who goes to the root is 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 to the value stored in index filho+1 ( 9b "on the side right "), so the child index is not incremented (in 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:

algorithm analysis (I did not test)
The question refers only to the construction phase of heap
how the tree is stored in the array

The correct answer is:

priority is given by the position these elements occupy in the tree (priority to the left by the lowest index)

References used to answer:

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 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

Additional links for online reference:

Wikipedia - Heapsort

Wikipedia - Steady sort

Wikipedia - Heapsort - the text is more complete and has a "step-by-step" algorithm)

Wikipedia - Heap

LANG, HANS WERNER - Heapsort

Sorting Algorithm Animations - Heap Sort