Bármely csomópont értéke nagyobb vagy egyenlő a gyerekeinek értékénél.
Ez azt jelenti, hogy a legnagyobb érték mindig a gyökérben van.
A max-heap egy:
Egy heap
pozícióhoz:
Kapcsolat | Index képlete |
---|---|
Szülő | (i - 1) / 2
|
Bal gyerek | 2 * i + 1
|
Jobb gyerek | 2 * i + 2
|
Művelet | Leírás | Időkomplexitás |
---|---|---|
insert(x)
|
Új elem beszúrása | O(log n) |
getMax()
|
Maximum lekérdezése (gyökér) | O(1) |
extractMax()
|
Maximum eltávolítása, és újrendezés | O(log n) |
heapify()
|
Max-heap visszaállítása a szabály szerint | O(log n) |
buildHeap()
|
N darab elem kupaccá alakítása | O(n) |
Egy max-heap lehet például így:
100 / \ 50 30 / \ / \ 20 10 5 1
Tömbként tárolva:
insert(x)
működésex
elemet a tömb végére.
extractMax()
class MaxHeap {
vector<int> heap;
void heapifyDown(int i) {
int n = heap.size();
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && heap > heap) largest = l;
if (r < n && heap > heap) largest = r;
if (largest != i) {
swap(heap, heap);
heapifyDown(largest);
}
}
void heapifyUp(int i) {
while (i > 0 && heap > heap) {
swap(heap, heap);
i = (i - 1) / 2;
}
}
public:
void insert(int val) {
heap.push_back(val);
heapifyUp(heap.size() - 1);
}
int extractMax() {
if (heap.empty()) throw runtime_error("Empty heap");
int maxVal = heap;
heap = heap.back();
heap.pop_back();
heapifyDown(0);
return maxVal;
}
int getMax() const {
if (heap.empty()) throw runtime_error("Empty heap");
return heap;
}
};
heapifyDown
a gyökérre.Időkomplexitás: O(n log n)
Tulajdonság | Érték |
---|---|
Legnagyobb elem | Gyökér (O(1)) |
Beszúrás ideje | O(log n) |
Törlés ideje | O(log n) |
Tárolási mód | Tömb (array) |
Sorrend | Nem teljes rendezés, csak részleges |