Heap
A heap is a complete tree, usually stored in an array, where every parent obeys a priority relation with its children. In a min-heap the smallest value stays at the root; in a max-heap the largest does.
ابدأ بهذا النموذج الذهني
A heap is a complete tree, usually stored in an array, where every parent obeys a priority relation with its children. In a min-heap the smallest value stays at the root; in a max-heap the largest does.
كيف يعمل، بلا مصطلحات زائدة
A heap is not fully sorted. It only guarantees the parent/child heap property.
Insert and remove-root repair the heap by bubbling a value up or down.
اقرأ الخوارزمية كسلسلة من القرارات
Append new value.
Bubble it upward while it violates the heap property.
For root removal, move the last value to root and bubble it down.
A min-heap used by Dijkstra always exposes the currently cheapest frontier node.
class MinHeap {
data = [];
push(value) {
this.data.push(value);
let i = this.data.length - 1;
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.data[p] <= this.data[i]) break;
[this.data[p], this.data[i]] = [this.data[i], this.data[p]];
i = p;
}
}
}لا تحفظ الصياغة. تتبع الحالة التي تتغير في كل سطر واربطها بالثابت الموضح أعلاه.
peek O(1), insert/remove O(log n)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
مناسب لـ
- Choose it when its dominant operations match your workload.
- Compare memory overhead as well as Big-O.
ما الذي يسوء عادةً
- Memorizing complexity without understanding representation.
- Ignoring worst-case shape or resizing/rebalancing costs.
صيغة إجابة احترافية
Do not say a heap is a sorted tree. Emphasize O(1) access to the best-priority item and O(log n) insertion/removal.
What problem does Heap solve?
A heap is a complete tree, usually stored in an array, where every parent obeys a priority relation with its children. In a min-heap the smallest value stays at the root; in a max-heap the largest does.
ماذا يجب أن أذكر عن التعقيد؟
Its typical cost here is peek O(1), insert/remove O(log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
ما الخطأ الأكثر شيوعاً؟
Memorizing complexity without understanding representation.