ALGORITHM READING NOTE

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.

TYPEData structureCATEGORYData StructuresDEPTHBeginnerTYPICAL COMPLEXITYpeek O(1), insert/remove O(log n)

SHORT INTERVIEW ANSWER

Start with this mental model

SIMPLE EXPLANATION

How it works, without unnecessary 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.

EXECUTION

Read the algorithm as a sequence of decisions

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 small example to keep in mind

A min-heap used by Dijkstra always exposes the currently cheapest frontier node.

READABLE JAVASCRIPT IMPLEMENTATIONJavaScript

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;
    }
  }
}

How to read this code

Do not memorize the syntax. Follow the state that changes on each line and connect it to the invariant described above.

COMPLEXITY

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.

WHEN TO USE IT

Good fit

Choose it when its dominant operations match your workload.
Compare memory overhead as well as Big-O.

COMMON MISTAKES

What usually goes wrong

Memorizing complexity without understanding representation.
Ignoring worst-case shape or resizing/rebalancing costs.

HOW TO EXPLAIN IT IN AN INTERVIEW

A professional answer shape

Do not say a heap is a sorted tree. Emphasize O(1) access to the best-priority item and O(log n) insertion/removal.

Problem→Core idea→Invariant / state→Big-O→Trade-off

QUICK INTERVIEW CHECK

What problem does Heap solve?

What should I mention about complexity?

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.

What is the most common mistake?

Memorizing complexity without understanding representation.

Continue readingPriority QueueHeap SortDijkstra

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; } } }