heapsort
Főnév
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é.
Algoritmus áttekintése
- Kupacépítés (build-heap) A bemeneti tömböt először max-heapé alakítjuk (minden szülő nagyobb vagy egyenlő a gyerekeinél). Ez O(n) idő alatt elvégezhető úgy, hogy a nem-levél csomópontokon „lesülylyedsz” (sift-down) a gyökértől a tömb közepe felé.
- Kiválogatásos fázis (sort) Amíg a kupac mérete nagyobb 1-nél:
- A gyökérben (arr[0]) lévő legnagyobb elemet kicseréljük az utolsó elemre (arr[size-1]).
- A kupac méretét eggyel csökkentjük (a legnagyobb most már a tömb végén rögzített).
- A gyökérnél újból „lesülylyedünk”, hogy helyreállítsuk a max-heap tulajdonságot O(log n) időben.
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.
Pseudokód
HEAPIFY(arr, n, i):
largest ← i
left ← 2*i + 1
right ← 2*i + 2
if left < n and arr[left] > arr[largest]:
largest ← left
if right < n and arr[right] > arr[largest]:
largest ← right
if largest ≠ i:
swap arr[i], arr[largest]
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[0], arr[i] # legnagyobb az utolsó helyre
HEAPIFY(arr, i, 0) # heapify a gyökérnél, kupacméret = i
C++ implementáció
#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[left] > arr[largest]) {
largest = left;
}
// Jobb gyerek nagyobb?
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// Ha a gyerekek között volt nagyobb elem, cserélünk és rekurzívan folytatjuk
if (largest != i) {
std::swap(arr[i], arr[largest]);
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[0], arr[i]); // 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
- A
heapifyegy adott gyökércsomópontnál helyreállítja a max-heap tulajdonságot O(log n) idő alatt. - A
heapSortelő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)). - Így a teljes időkomplexitás Θ(n log n), a helyigény O(1).
Idő- és helykomplexitás
| 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) |
- Stabilitás: Nem stabil, mert a csere nem tartja meg az egyenlő kulcsú elemek eredeti sorrendjét.
- In-place: Igen, csak néhány segédváltozót használ.
Összehasonlítás más rendezőkkel
| 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 |
- A heapsort garantált Θ(n log n), de konstans tényezője miatt gyakran lassabb a jól implementált quicksortnál.
- A mergesort stabil, de extra memóriát igényel.
Mikor érdemes használni?
- Ha fontos a garantált Θ(n log n) futásidő legrosszabb esetben is.
- Ha korlátozott az extra memóriahasználat (in-place megoldás).
- Ha nem szükséges a stabilitás.
Ö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.