Course contentsShow
← Computer Science
Lesson 617 of 2,87214. Heaps and Priority QueuesFree lesson

Load Balancing Systems

Distribute tasks to servers by tracking server loads in a min-heap to assign work to least-loaded servers.

Load Balancing Systems

You'll learn how to use a min-heap to distribute tasks fairly across multiple servers by always assigning work to the least-loaded one.


The Core Idea

Imagine you run a data center with many servers, and tasks keep arriving that need processing. How do you decide which server gets the next task? A naive approach might just cycle through servers, but some tasks take longer than others—you'd end up with some servers overloaded while others sit idle.

The smart solution: track each server's current load (total work assigned) in a min-heap. The server at the heap's root always has the smallest load. When a new task arrives, assign it to that server, update its load, and let it bubble down to its proper position. This guarantees you always pick the least-busy server in O(log n) time.

How It Works

  1. Initialize: Create a min-heap where each element is a server with its current load (initially 0)
  2. Task arrives: Extract the minimum (least-loaded server)
  3. Assign task: Add the task's workload to that server's load
  4. Reinsert: Put the updated server back in the heap (it will bubble down to maintain heap order)

This is essentially using extract-min, modifying the value, then insert—or more efficiently, peeking at the root, updating it, and calling heapify-down.

Why This Matters

Without the heap, you'd need O(n) time to scan all servers for the minimum load. With the heap, it's O(log n) per assignment. For a system handling thousands of tasks per second, this efficiency is critical.

Key Takeaway: A min-heap lets load balancing systems efficiently track and assign work to the least-loaded server, ensuring fair distribution with logarithmic-time operations.