Domů » Informatika » Algoritmus » Řadící algoritmus » Heap Sort (řazení pomocí haldy)

Heap Sort (řazení pomocí haldy)

Heap sort je řadící algoritmus podobný selection sortu, ale mnohem efektivnější. Algoritmus je založený na datové struktuře zvané halda (heap), což je úplný binární strom, ve kterém pro každý uzel platí, že je větší než oba jeho potomci.

Reprezentace v poli

Nechť A je pole. Každý jeho prvek bude představovat jeden uzel haldy. Kořenem haldy bude první prvek pole na indexu 0 a každý uzel na indexu n bude mít své dva potomky na indexu € 2n+1 € (levý) a € 2n+2 € (pravý). Jsou-li oba tyto indexy mimo rozsah pole, jedná se o list.

Tato reprezentace je využita v implementaci algoritmu heap sort.

Implementace (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Implementace algoritmu heap sort.
  3.  * @param input pole k seřazení
  4.  * @param ascending TRUE pro vzestupné řazení, FALSE pro sestupné
  5.  */
  6. public static <T extends Comparable<? super T>> void heapSort(final T[] input, final boolean ascending)
  7. {
  8.   // požadovaný směr řazení
  9.  
  10.   final int dir = ascending ? -1 : 1;
  11.  
  12.   // inicializovat haldu ve vstupním poli
  13.  
  14.   for (int i = (input.length / 2) - 1; i >= 0; i--)
  15.   {
  16.     HeapSort.sift(input, i, input.length - 1, dir);
  17.   }
  18.  
  19.   // seřadit pole postupným posunem prvků na správné místo
  20.  
  21.   for (int i = input.length - 1; i > 0; i--)
  22.   {
  23.     // vložit prvek "i" na vrchol
  24.     HeapSort.swap(input, i, 0);
  25.     // prosít prvek na správé místo
  26.     HeapSort.sift(input, 0, i - 1, dir);
  27.   }
  28. }
  29.  
  30. /**
  31.  * Metoda pro opravu haldy - umístí zvolený prvek na správné místo.
  32.  * @param input pole k seřazení
  33.  * @param iTop index vrcholu haldy
  34.  * @param iBottom poslední index haldy
  35.  * @param dir směr řazení (-1 vzestupně, +1 sestupně)
  36.  */
  37. private static <T extends Comparable<? super T>> void sift(final T[] input, final int iTop, final int iBottom, final int dir)
  38. {
  39.   int iRoot = iTop;
  40.   int iChild = (iRoot * 2) + 1;
  41.  
  42.   while (iChild <= iBottom)
  43.   {
  44.     // vyhledat místo pro vložení hodnoty
  45.  
  46.     if ((iChild < iBottom) && (input[iChild].compareTo(input[iChild + 1]) == dir))
  47.     {
  48.       iChild++;
  49.     }
  50.  
  51.     if (input[iRoot].compareTo(input[iChild]) == dir)
  52.     {
  53.       // prohodit oba prvky
  54.       HeapSort.swap(input, iRoot, iChild);
  55.       // pokračovat v prosívání od potomka
  56.       iRoot = iChild;
  57.       iChild = (iRoot * 2) + 1;
  58.       continue;
  59.     }
  60.  
  61.     // ukončit prosívání
  62.     break;
  63.   }
  64. }
  65.  
  66. /**
  67.  * Metoda pro prohození dvou prvků.
  68.  * @param input vstupní pole
  69.  * @param i1 první index
  70.  * @param i2 druhý index
  71.  */
  72. private static <T extends Comparable<? super T>> void swap(final T[] input, final int i1, final int i2)
  73. {
  74.   final T temp = input[i2];
  75.   input[i2] = input[i1];
  76.   input[i1] = temp;
  77. }

Reference