Interview OS
Back to Algorithms & Data Structures

Library

Heaps / priority queues

O(log n) min/max extraction.

Tree

Overview

A heap is a complete binary tree maintaining the heap property, giving O(log n) insert/extract and O(1) peek at the min or max. It's the concrete data structure behind priority queues and heapsort.

How it works

Tree
InsertStoreExtractOutputPushO(log n)Array heapchild=2i+1Pop rootO(log n)Use
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Push

    • Add at the end and sift up.
  2. 2

    Array heap

    • A complete binary tree in an array.
  3. 3

    Pop root

    • Remove the min/max and sift down.
  4. 4

    Use

    • Priority queues and top-k.
    • Example: Dijkstra

Overview

A complete binary tree maintaining the heap property; root is the min (or max).

When to use it

  • Top-k
  • Dijkstra / Prim
  • Streaming medians (two heaps)

Common pitfalls

  • Confusing min vs max heap
  • Rebuilding instead of sift-down

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides