Heapsort

Heapsort (řazení haldou) je jedním z nejefektivnějších řadících algoritmů založených na porovnávání prvků s asymptotickou složitostí $O(n \\cdot \\log{n})$ . Jelikož je tato složitost zaručená, tak je heapsort vhodnější pro použití v real-time systémech než v průměrném případě rychlejší quicksort, jenž však může dosahovat složitosti v nejhorším případě až $O(n^{2})$ .

Princip

Základem heapsortu je binární halda, jejíž základní vlastností je, že se chová jako prioritní fronta. Pokud z prioritní fronty postupně odebíráme prvky, tak je zřejmé, že tím dochází k jejich řazení. Celý postup se skládá z následujících kroků:

Postavme haldu nad zadaným polem.
Utrhněme vrchol haldy (prvek s nejvyšší prioritou - nejvyšší nebo nejnižší prvek dle způsobu řazení).
Prohoďme utržený prvek s posledním prvkem haldy.
Zmenšeme haldu o 1 (prvky řazené dle priority na konci pole jsou již seřazené).
Opravme haldu tak, aby splňovala požadované vlastnosti (přestaly platit v momentě prohození prvků).
Dokud má halda prvky GOTO: 2.
Pole je seřazené v opačném pořadí, než je priorita prvků.

Heapsort - vizualizace

Kód

     /**
      * Heapsort - razeni haldou
      * @param array pole k serazeni
      * @param descending true, pokud ma byt pole serazeno sestupne, false pokud vzestupne
      */
     public static void heapSort(Comparable[] array, boolean descending) {
         for (int i = array.length / 2 - 1; i >= 0; i--) {
             repairTop(array, array.length - 1, i, descending ? 1 : -1);
         }
         for (int i = array.length - 1; i > 0; i--) {
             swap(array, 0, i);
             repairTop(array, i - 1, 0, descending ? 1 : -1);
         }
     }
 
     /**
      * Umisti vrchol haldy na korektni misto v halde (opravi haldu)
      * @param array pole k setrizeni
      * @param bottom posledni index pole, na ktery se jeste smi sahnout
      * @param topIndex index vrsku haldy
      * @param order smer razeni 1 == sestupne, -1 == vzestupne
      */
     private static void repairTop(Comparable[] array, int bottom, int topIndex, int order) {
         Comparable tmp = array[topIndex];
         int succ = topIndex * 2 + 1;
         if (succ < bottom && array[succ].compareTo(array[succ + 1]) == order) {
             succ++;
         }
 
         while (succ <= bottom && tmp.compareTo(array[succ]) == order) {
             array[topIndex] = array[succ];
             topIndex = succ;
             succ = succ * 2 + 1;
             if (succ < bottom && array[succ].compareTo(array[succ + 1]) == order) {
                 succ++;
             }
         }
         array[topIndex] = tmp;
     }
 
     /**
      * Prohodi prvky haldy
      * @param array pole
      * @param left index prvniho prvku
      * @param right index druheho prvku
      */
     private static void swap(Comparable[] array, int left, int right) {
         Comparable tmp = array[right];
         array[right] = array[left];
         array[left] = tmp;
     }

 /**
  * Razeni haldou (sestupne)
  * @param array pole k serazeni
  * @param size velikost pole
  */
 void heapsort(int array[], int size){
     for (int i = size/2 - 1; i >= 0; i--) {
         repairTop(array, size - 1, i);
     }
     for (int i = size - 1; i > 0; i--) {
         swap(array, 0, i);
         repairTop(array, i - 1, 0);
     }
 }
 
 /**
  * Umisti vrchol haldy na korektni misto v halde (opravi haldu)
  * @param array - pole k setrizeni
  * @param bottom - posledni index pole, na ktery se jeste smi sahnout
  * @param topIndex - index vrsku haldy
  */
 void repairTop(int array[], int bottom, int topIndex) {
     int tmp = array[topIndex];
     int succ = topIndex*2 + 1;
     if (succ < bottom && array[succ] > array[succ+1]) succ++;
     
     while (succ <= bottom && tmp > array[succ]) {
         array[topIndex] = array[succ];
         topIndex = succ;
         succ = succ*2 + 1;
         if (succ < bottom && array[succ] > array[succ+1]) succ++;
     }
     array[topIndex] = tmp; 
 }
 
 /**
  * Prohodi prvky v zadanem poli
  * @param array pole
  * @param left prvek 1
  * @param right prvek 2
  */
 void swap(int array[], int left, int right) {
     int tmp = array[right]; 
     array[right] = array[left];
     array[left] = tmp;         
 }

         /**
          * Razeni haldou (sestupne)
          * @param array pole k serazeni
          */
         public static void Heapsort(int[] array)
         {
             for (int i = array.Length / 2 - 1; i >= 0; i--)
             {
                 RepairTop(array, array.Length - 1, i);
             }
             for (int i = array.Length - 1; i > 0; i--)
             {
                 Swap(array, 0, i);
                 RepairTop(array, i - 1, 0);
             }
         }
 
         /**
          * Umisti vrchol haldy na korektni misto v halde (opravi haldu)
          * @param array - pole k setrizeni
          * @param bottom - posledni index pole, na ktery se jeste smi sahnout
          * @param topIndex - index vrsku haldy
          */
         private static void RepairTop(int[] array, int bottom, int topIndex)
         {
             int tmp = array[topIndex];
             int succ = topIndex * 2 + 1;
             if (succ < bottom && array[succ] > array[succ + 1]) succ++;
 
             while (succ <= bottom && tmp > array[succ])
             {
                 array[topIndex] = array[succ];
                 topIndex = succ;
                 succ = succ * 2 + 1;
                 if (succ < bottom && array[succ] > array[succ + 1]) succ++;
             }
             array[topIndex] = tmp;
         }
 
         /**
          * Prohodi prvky v zadanem poli
          * @param array pole
          * @param left prvek 1
          * @param right prvek 2
          */
         private static void Swap(int[] array, int left, int right)
         {
             int tmp = array[right];
             array[right] = array[left];
             array[left] = tmp;
         }

Rozbor kódu

Binární halda
(nižší hodnota má vyšší prioritu)

Vlastnosti haldy

Halda je binární strom s rekurzivní vlastností býti haldou. Rekurzivita vlastnosti značí, že i každý podstrom haldy je taktéž haldou. V každé haldě také platí, že otec má vždy vyšší hodnotu než jeho potomci. Při její implementaci polem pak také platí, že pokud je otec na indexu , tak jsou jeho potomci na indexech 2i+1 a 2i+2 (indexováno od 0). Z tohoto uspořádání plyne, že tvar haldy je pyramida s částečně useknutou pravou stranou základny.

Funkce repairTop

Funkce repair top opravuje vnitřní strukturu haldy – řazení prvků – v okamžiku, kdy víme, že je vrchol haldy umístěn na nesprávné pozici. Toho je docíleno tím, že algoritmus vždy porovná otce s oběma potomky a pokud má otec nižší prioritu než některý ze synů (případně než oba synové), tak jej prohodí s vyšším z nich. Jelikož ale mohlo dojít pouze k přenesení nerovnováhy o úroveň níže, tak algorimus musí opravit i tuto podhaldu. Celé procedura terminuje v okamžiku, kdy buď příslušný otec již nemá žádné potomky, nebo je vlastnost býti haldou zaručena (otec má vyšší prioritu než oba synové).

Funkce heapsort

Jak jsme již zmínili, tak býti haldou je rekurzivní vlasností. Proto nejprve opravíme všechny netriviální podhaldy od těch nejmenších, až po ty největší. Protože následníci daného prvku se nachází na indexech 2i+1 a 2i+2 , máme jistotu, že prvek se na indexeu ( array.length/2 - 1 ) nachází vrchol nějaké netriviální podhaldy, kterou můžeme opravit.

V okamžiku, kdy opravíme všechny podhaldy (a haldu samotnou), tak můžeme seřadit pole pomocí výše zmíněné procedury (odstraň vrchol haldy, prohoď ho s posledním prvkem, zkrať haldu, oprav haldu).

Princip

Kód

Rozbor kódu

Vlastnosti haldy

Funkce repairTop

Funkce heapsort

Doporučujeme