Heapsort (sortowanie przez kopcowanie)
Aby zrozumieć ten algorytm należy najpierw zapoznać się ze strukturą zwaną "kopcem". W szczególności ważna jest operacja usuwania elementu minimalnego. Właściwie to cała filozofia tego sortowania opiera się na niej. Usuwamy element, aż kopiec stanie się pusty. Wpisujemy usuwany element na kolejne miejsce w docelowej tablicy. Zobaczmy jak wygląda to w praktyce
public static void Sort(int[] array) {
Heap heap = new Heap(array);
for (int k = 0; k < array.Length; k++)
array[k] = heap.DeleteMin();
}
Jak widzimy, tworzymy nowy kopiec i po kolei usuwamy z niego elementy minimalne. Ile czasu zajmuje to sortowanie? Zastanówmy się. Budowa kopca jak wiemy trwa O(n). Przechodzimy wszystkie elementy, każdorazowo przywracając porządek kopca czyli O (n * logn). Razem wychodzi O(n * logn). Czyli rezultat bardzo dobry. To tyle o tym sortowaniu.
