What Is a Heap (Data Structure)?

A heap is a complete binary tree where every parent is ordered relative to its children: in a min-heap the smallest value is at the root, in a max-heap the largest. It gives O(1) access to the min/max and O(log n) insert and remove, which makes it the basis of priority queues.

The concept

Heaps are stored in a plain array: the children of index i are at 2i+1 and 2i+2, and the parent is at (i−1)/2.

Insert appends at the end and bubbles up; removing the root moves the last item to the top and sinks it down.

Min-heap as tree and array

Practical examples

Minimal min-heap

class MinHeap {
  a = []
  push(v) { this.a.push(v); let i = this.a.length - 1
    while (i > 0) { const p = (i - 1) >> 1; if (this.a[p] <= this.a[i]) break; [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p } }
  pop() { const top = this.a[0], last = this.a.pop()
    if (this.a.length) { this.a[0] = last; let i = 0
      for (;;) { let m = i, l = 2*i+1, r = l+1
        if (l < this.a.length && this.a[l] < this.a[m]) m = l
        if (r < this.a.length && this.a[r] < this.a[m]) m = r
        if (m === i) break; [this.a[m], this.a[i]] = [this.a[i], this.a[m]]; i = m } }
    return top }
}

Python heapq

import heapq
h = []; heapq.heappush(h, 5); heapq.heappush(h, 1)
heapq.heappop(h)  # 1

Top-k largest

heapq.nlargest(3, nums)

Common mistakes

• Expecting a heap to be fully sorted.
• Using a heap for searching arbitrary values (O(n)).
• Mixing min-heap and max-heap logic.

Key takeaways

• Root is min or max.
• Array-backed, O(log n) push/pop.
• Powers priority queues and heap sort.

FAQ

Heap vs BST?

Heaps give fast access to the extreme only; BSTs support ordered search.

Heap memory vs data structure heap?

Unrelated: the call-stack/heap memory area versus this tree structure.