Heap Sort
Napsal: Altaibayar Tseveenbayar http://blog.nadam.eu/
Halda je v informatice stromová datová struktura splňující tzv. vlastnost haldy: pokud je B potomek A, pak x(A) >= x(B). To znamená, že v kořenu stromu je vždy prvek s nejvyšším klíčem (klíč udává funkce x). Taková halda se pak někdy označuje jako max heap (heap je v angličtině halda), halda s reverzním pořadím prvků se analogicky nazývá min heap. Díky této vlastnosti se haldy často používají na implementaci prioritní fronty. Efektivita operací s haldou je klíčová pro mnoho algoritmů.
Operace s haldou
· INSERT - přidání nového prvku do haldy
· DELETE MAX - vyjmutí kořenu v max heap nebo v min heap
· MAX - vrátí minimální resp. maximální klíč v haldě
· MAKE - dostane pole N prvku a vytvoří z nich haldu
Popis haldy
Haldu bychom mohli tedy definovat jako datovou struktura splňující dvě základní podmínky:
· lokální podmínku na uspořádání - prvek reprezentující otce je menší než prvek reprezentovaný synem apod.
· strukturální podmínku na stromy, ze kterých jsou vytvořené
Právě podle těchto podmínek se haldy rozdělují na d-regulární, Fibonacciho, Leftist a další (mohou se lišit jak lokální, tak strukturální podmínkou).
Jak již bylo naznačeno, rozlišujeme haldy Min-Heap a Max-Heap.
· U Min-Heap jsou klíče dětí jednoho uzlu vždy větší než klíče svého otce. To způsobuje, že na kořenech stromu lze nalézt pouze prvek s minimálním klíčem.
· Opačně je pro Max-Heap stanovena podmínka, že klíče dětí jednoho uzlu musí být vždy menší než klíče jejich otce. Zde se na kořeni stromu vždy nachází prvek s maximálním klíčem.
Příklady Max-Heap a Min-Heap:
Obousměrné haldy (Double heaps)
Často se stává, že halda má zobrazit podmínku v obou směrech. V tomto případě se jednoduše vytvoří haldy dvě a uspořádají se podle větší a menší relace. Taková struktura je pak označována jako Double heap nebo krátce Deap.
Při použití Double heaps je třeba dávat pozor na to, že ne každá implementace haldy si pro jednotlivé operace zachová svůj průběh. Například Fibonacciho haldy s konstantním amortizovaným průběhem podporují pouze decreaseKey pro snížení klíčů. Všeobecný changeKey pro změnu klíče, který je vyžadován v případě Double heap, potřebuje ale amortizované minimálně logaritmický čas.
Variantou hald, které splňují podmínku haldy pouze částečně, nebo odchylně jsou tzv. Min-Max-Heap. Jedná se o Double heap, které díky odchylné formě podmínky haldy mohou udržovat data pouze v jednom stromu.
Přidá prvek do haldy
/// <summary>
/// Adds item to heap
/// </summary>
/// <param name="heap">array of heap</param>
/// <param name="data">data, that are you adding to heap</param>
/// <param name="size">size of heap, before adding</param>
/// <returns>new heap with added value</returns>
public int[] Add(int[] heap, int data, int size)
{
if (heap.Length == size)
{
Console.WriteLine("ERROR : Heap is full");
return heap;
}
//j - index of son
//p - index of parent
//d - temporary int for swapping
int j, p, d;
//says if it'll continue with "upbubbling" new value
bool cont;
//you are adding, so increment size
size++;
//add avlue to the end of array(tree)
heap[size - 1] = data;
//index of added value
j = size - 1;
//if i'm not head of tree
cont = j > 0;
while (cont)
{
//index of parent
p = j / 2;
if (heap[j] > heap[p]) //son is bigger than parent, so change'em
{
//swap parent and son
d = heap[j];
heap[j] = heap[p];
heap[p] = d;
//now go one level higher
j = p;
//am i still not on the top???
cont = j > 0;
}
else
{
cont = false;
}
}
return heap;
}
Odstrani maximalni prvek z haldy
/// <summary>
/// Deletes maximal item in heap
/// </summary>
/// <param name="heap">array of heap</param>
/// <param name="size">size of heap</param>
/// <returns>new heap, without max</returns>
public int[] DeleteMaximum(int[] heap, int size)
{
if (heap.Length == 0)
{
Console.WriteLine("ERROR : Size is bigger than array length");
return heap;
}
int j, n, d;
//n - index of higher son
//j - index of father
//d - temporary int for swapping
bool cont;
heap[0] = heap[size - 1];
size--;
j = 0;
cont = (2 <= size);
while (cont)
{
if (j == 0) { n = 1; } //array is indexed from 0
else { n = 2 * j; }
if (n < size && heap[n + 1] > heap[n])
n++; //n is index of higher son
if (heap[j] < heap[n])
{
d = heap[j];
heap[j] = heap[n];
heap[n] = d;
j = n;
cont = (2 * j <= size);
}
else
{
cont = false;
}
}
return heap;
}
Seřadí haldu (musí byt předtím postavena)
/// <summary>
/// Sorts Heap
/// </summary>
/// <param name="heap">array of heap</param>
/// <param name="size">size of array(heap)</param>
/// <returns>sorted heap</returns>
public int[] Sort(int[] heap, int size)
{
if (heap.Length < size)
{
Console.WriteLine("ERROR : Size is bigger than array length");
return heap;
}
for (int count = size - 1; count > 0; count--)
{
int tmp = heap[0];
heap[0] = heap[count];
heap[count] = tmp;
bubble(heap, count, 0);
}
return heap;
}
private void bubble(int[] heap, int size, int count)
{
int i, j = count;
do
{
i = j;
if ((2 * i + 1) < size && heap[2 * i + 1] > heap[j])
j = 2 * i + 1;
if ((2 * i + 2) < size && heap[2 * i + 2] > heap[j])
j = 2 * i + 2;
//swap(i,j);
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
} while (i != j);
}
Postaví haldu z pole
/// <summary>
/// Builds heap from array of integer
/// </summary>
/// <param name="heap">input array</param>
/// <param name="size">size of heap</param>
/// <returns>heap, made from input array</returns>
public int[] Build(int[] heap, int size)
{
if (heap.Length < size)
{
Console.WriteLine("ERROR : Size is bigger than array length");
return heap;
}
for (int count = size - 1; count >= 0; count--)
bubble(heap, size, count);
return heap;
}
Zdroje:
· www.wikipedia.org
· Pavel Topfer – Algoritmy a programovaci techniky
· Mike Copley - http://www2.hawaii.edu/~copley/665/HSApplet.html
PDF verze
Animace