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.