The “Other” Heap

In DSA, a “Heap” is a priority queue. In Systems, the “Heap” is the region of memory for dynamic allocation (malloc/new). Confusing? Yes. But they are related.

1. How malloc works

The OS gives your program a big block of memory. You need to slice it up.

• Request: malloc(16) → “Give me 16 bytes”.
• Free: free(ptr) → “I’m done with this”.

2. The Data Structure: Free List

To know which parts are free, allocators use a Linked List (Free List) embedded in the free blocks themselves. To find the best fit efficiently, they often use Segregated Free Lists (Arrays of Lists) or Heaps (Binary Heaps) to track chunk sizes.

3. Fragmentation

• External: Enough total memory, but no single block big enough. (Swiss Cheese memory).
• Internal: Allocated 16 bytes but user only needed 10.

4. Interactive: Allocator Visualizer

Simulate malloc and free. See how the Free List changes.

Heap Empty. 100 bytes available.

5. The Buddy System (Linux)

To reduce fragmentation, Linux uses the Buddy System.

• Memory is split into powers of 2 (4KB, 8KB, 16KB…).
• If you need 7KB, it splits a 16KB block into two 8KB “buddies”. Gives you one.
• When you free it, if the buddy is also free, they merge back into 16KB instantly.