Кӯчаи дуӣ
Кӯчаи дуӣ (binary heap) — ин дарахти дуии овезон аст, ки барои он шартҳо иҷро мешаванд:
Ҳамчунин кӯча як дарахти дуии қариб пурра мебошад:
Кӯчаро қулай аст дар массиви нигоҳ дорем.
Баландии кӯча ба баробар аст, бинобар ин амалиётҳои асосӣ зуд иҷро мешаванд.
Мо ҳамеша хосияти кӯча-ро нигоҳ медорем, ки дар он ҳар падар фарзандони худ аст. Ба шарофати ин максимум ҳамеша дар реша ҷойгир аст.
sift_up(i) — боло бардоштанҲангоми push истифода мешавад.
Алгоритм:
Азбаски баландии кӯча аст, амалиёт бо кор мекунад.
sift_down(i) — поён ҷумбонданҲангоми pop истифода мешавад.
Алгоритм:
Ҳамчунин бо кор мекунад.
struct Heap {
vector<int> a;
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }
void sift_up(int i) {
while (i > 0 && a[parent(i)] < a[i]) {
swap(a[parent(i)], a[i]);
i = parent(i);
}
}
void sift_down(int i) {
while (true) {
int l = left(i);
int r = right(i);
int best = i;
if (l < (int)a.size() && a[l] > a[best]) {
best = l;
}
if (r < (int)a.size() && a[r] > a[best]) {
best = r;
}
if (best == i) {
break;
}
swap(a[i], a[best]);
i = best;
}
}
void push(int x) {
a.push_back(x);
sift_up((int)a.size() - 1);
}
int top() {
return a[0];
}
void pop() {
a[0] = a.back();
a.pop_back();
if (!a.empty()) {
sift_down(0);
}
}
bool empty() {
return a.empty();
}
int size() {
return (int)a.size();
}
};