heapsort (tsz. heapsorts)
A heapsort egy összehasonlítás-alapú, in-place rendező algoritmus, amely egy bináris kupac (heap) adatszerkezetre épül. Legfőbb előnye, hogy garantáltan O(n log n) időben fut, és nem igényel extra tömböt a rendezéshez (O(1) kiegészítő hely). Hátránya viszont, hogy nem stabil (egyenlő kulcsú elemek relatív sorrendje változhat), és konstans tényezője valamivel nagyobb, mint a quicksorté.
Végül a tömb rendezett (növekvő) lesz, mert mindig a maradékból vettük ki a legnagyobbat és tettük a végére.
HEAPIFY(arr, n, i):
largest ← i
left ← 2*i + 1
right ← 2*i + 2
if left < n and arr > arr:
largest ← left
if right < n and arr > arr:
largest ← right
if largest ≠ i:
swap arr, arr
HEAPIFY(arr, n, largest)
HEAPSORT(arr, n):
# 1. Build max-heap
for i = floor(n/2) - 1 downto 0:
HEAPIFY(arr, n, i)
# 2. Extract elements from heap one by one
for i = n - 1 downto 1:
swap arr, arr # legnagyobb az utolsó helyre
HEAPIFY(arr, i, 0) # heapify a gyökérnél, kupacméret = i
#include <iostream>
#include <vector>
#include <algorithm> // std::swap
// A kupac lesülylyesztő függvénye (max-heap)
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
// Bal gyerek nagyobb?
if (left < n && arr > arr) {
largest = left;
}
// Jobb gyerek nagyobb?
if (right < n && arr > arr) {
largest = right;
}
// Ha a gyerekek között volt nagyobb elem, cserélünk és rekurzívan folytatjuk
if (largest != i) {
std::swap(arr, arr);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = static_cast<int>(arr.size());
// 1. Max-heap kialakítása
for (int i = n/2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
// 2. Rendezettség: legnagyobb kivenni és heapify
for (int i = n - 1; i > 0; --i) {
std::swap(arr, arr); // a gyökérből az utolsó elemre
heapify(arr, i, 0); // kupacméret = i
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::cout << "Eredeti tömb: ";
for (int x : arr) std::cout << x << ' ';
std::cout << '\n';
heapSort(arr);
std::cout << "Rendezett tömb: ";
for (int x : arr) std::cout << x << ' ';
std::cout << '\n';
return 0;
}
Megjegyzések a kódhoz
heapify egy adott gyökércsomópontnál helyreállítja a max-heap tulajdonságot O(log n) idő alatt.heapSort először lineáris idejű kupacépítést végez (O(n)), majd n−1 lépésben kiveszi a gyökérből a legnagyobbat és újra-heapifyolja (összesen O(n log n)).
| Művelet | Legjobb | Átlagos | Legrosszabb | Extra hely |
|---|---|---|---|---|
| Kupacépítés | Θ(n) | Θ(n) | Θ(n) | O(1) |
| Kiválogatás fázis | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(1) |
| Összesen | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(1) |
| Tulajdonság | Heapsort | Quicksort | Mergesort |
|---|---|---|---|
| Idő átlag | Θ(n log n) | Θ(n log n) | Θ(n log n) |
| Idő legrosszabb | Θ(n log n) | Θ(n²) | Θ(n log n) |
| Helyigény | O(1) | O(log n) | O(n) |
| Stabilitás | Nem | Nem (gyakran) | Igen |
Összefoglalás A heapsort egy in-place, összehasonlítás-alapú rendező algoritmus, amely bináris max-heap használatával garantáltan Θ(n log n) időben rendez. Előnye a kis extra memóriaigény és a legrosszabb esetben is biztos határidő, hátránya viszont, hogy nem stabil és konstans tényezője nagyobb, mint a quicksorté. C++-ban néhány száz soros kód segítségével könnyen implementálható és robosztus választás ott, ahol a determinisztikus teljesítmény fontos.