binary heap (tsz. binary heaps)
A binary heap (bináris kupac) egy olyan teljes bináris fa, amely kielégíti a heap-tulajdonságot, vagyis minden szülő-gyerek kapcsolatnál az alábbiak igazak:
A binary heap gyakori alapja a prioritási soroknak (priority queues), illetve a Heapsort algoritmusnak.
heapheapheapheap
| Művelet | Leírás | Időkomplexitás |
|---|---|---|
insert(x)
|
Új elem hozzáadása | O(log n) |
getMin() / getMax()
|
Gyökér visszaadása | O(1) |
extractMin() / extractMax()
|
Gyökér eltávolítása és újrarendezés | O(log n) |
heapify()
|
Egész fa újrarendezése | O(log n) |
buildHeap()
|
Lista átalakítása kupaccá | O(n) |
5
/ \
10 8
/ \ /
15 12 11
Tömbként tárolva:
Minden szülő kisebb a gyerekeinél → min-heap.
insert(x)x-et a tömb végére.
extractMin() (min-heap)heap elemet.
heapify(i) (top-down)void heapify(vector<int>& heap, int i) {
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < heap.size() && heap < heap) smallest = l;
if (r < heap.size() && heap < heap) smallest = r;
if (smallest != i) {
swap(heap, heap);
heapify(heap, smallest);
}
}
buildHeap() (bottom-up)void buildHeap(vector<int>& heap) {
for (int i = heap.size() / 2 - 1; i >= 0; --i) {
heapify(heap, i);
}
}
Ez O(n) időben alakít át egy rendezetlen tömböt egy min-heap struktúrává.
| Adatszerkezet | Insert | Extract Min | Decrease Key | Merge |
|---|---|---|---|---|
| Binary heap | O(log n) | O(log n) | O(log n) | O(n) |
| Binomiális heap | O(log n) | O(log n) | O(log n) | O(log n) |
| Fibonacci heap | O(1) | O(log n)* | O(1) | O(1) |
class BinaryHeap {
vector<int> heap;
void heapifyDown(int i);
void heapifyUp(int i);
public:
void insert(int val);
int getMin();
int extractMin();
};
A binary heap egy hatékony, tömbben tárolt prioritási sor, amely lehetővé teszi a minimum vagy maximum gyors elérését és módosítását. Használata egyszerűbb, mint a haladóbb struktúráké (pl. Fibonacci heap), és a legtöbb gyakorlati célra tökéletesen megfelel.