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.
Beginne mit diesem mentalen Modell
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.
So funktioniert es – ohne unnötigen Jargon
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.
Lies den Algorithmus als Folge von Entscheidungen
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;
}
}
}Lerne die Syntax nicht auswendig. Folge dem Zustand, der sich in jeder Zeile ändert, und verbinde ihn mit der oben beschriebenen Invariante.
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.
Gut geeignet
- Choose it when its dominant operations match your workload.
- Compare memory overhead as well as Big-O.
Was typischerweise schiefgeht
- Memorizing complexity without understanding representation.
- Ignoring worst-case shape or resizing/rebalancing costs.
Struktur einer professionellen Antwort
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.
Was sollte ich zur Komplexität erwähnen?
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.
Was ist der häufigste Fehler?
Memorizing complexity without understanding representation.