Course contentsShow
← System Design
Lesson 1847 of 1,91944. Real-World System: Web CrawlerFree lesson

Heap-Based Priority Queue Implementation

Using min-heaps or similar structures to efficiently select next URLs based on priority scores or scheduled fetch times.

Heap-Based Priority Queue Implementation

You'll learn how min-heaps efficiently manage URL priorities in a web crawler's front queue.

The Core Idea

In a distributed web crawler, not all URLs deserve equal attention. Some pages (like news sites) need frequent recrawling, while others (like archived documents) can wait. A heap-based priority queue lets you instantly retrieve the highest-priority (or earliest-scheduled) URL without scanning thousands of candidates.

Think of it like an emergency room: patients aren't seen first-come-first-served—the most urgent case always goes next. A min-heap organizes URLs so the "next to crawl" bubbles to the top in O(log n) time.

How It Works

A min-heap is a binary tree where each parent node has a smaller value than its children. For crawlers, you typically store:

  • Priority score (lower = more urgent), or
  • Next fetch timestamp (earliest time first)

When you insert a new URL with priority 5, it's placed at the heap's end and "bubbles up" until heap order is restored. When you extractMin, the root (lowest priority/earliest time) is removed, and the last element "bubbles down" to maintain structure.

Why Heaps Beat Alternatives

  • Sorted arrays: Insertion is O(n) — too slow when millions of URLs arrive.
  • Unsorted queues: Finding the minimum is O(n) — unacceptable per fetch.
  • Heaps: Both insert and extract-min are O(log n), balancing writes and reads beautifully.

In a crawler's front queue (priority management layer), the heap ensures that when you ask "What URL should I crawl next?", you get the answer in microseconds, even with millions of pending URLs.

Key Takeaway:
A min-heap-based priority queue gives O(log n) insertion and extraction, making it ideal for selecting the next URL to crawl based on priority scores or scheduled fetch times in massive-scale web crawlers.