Binary Heap

DSA · Heaps

Theory

A binary heap is a complete binary tree stored in an array that satisfies the heap property: in a min-heap every parent is smaller than or equal to its children, so the minimum is always at index 0. Inserting appends the item at the end and "sifts it up"; removing the minimum moves the last item to the root and "sifts it down". Both take O(log n), and building a heap from n items takes O(n).

Why we use it

Heaps give constant-time access to the smallest (or largest) item with logarithmic updates, which is exactly what priority queues need.

When to use it

Use heaps for priority queues, scheduling, Dijkstra's algorithm, running medians, merging k sorted lists and top-k problems.

How it works

  1. Insert at the end of the array
  2. Parent > new value? (min-heap)? Yes: Swap with parent (sift up). No: Stop.
  3. Pop: move last item to root
  4. Sift down: swap with the smaller child until ordered
  5. Root is always the minimum

Syntax

Array layout: parent(i) = (i-1)//2, children 2i+1 and 2i+2
push:  append, sift up      O(log n)
pop:   swap root with last, remove, sift down  O(log n)
peek:  heap[0]              O(1)

Example

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        a[0], a[-1] = a[-1], a[0]
        smallest = a.pop()
        i = 0
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < len(a) and a[l] < a[m]: m = l
            if r < len(a) and a[r] < a[m]: m = r
            if m == i: break
            a[i], a[m] = a[m], a[i]
            i = m
        return smallest

h = MinHeap()
for x in [7, 2, 9, 4, 1, 8]:
    h.push(x)
print("Heap array:", h.a)
print("Removed in order:", [h.pop() for _ in range(6)])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic