How does memory on the heap get exhausted?

It is very likely that pointers returned by new on your platform are 16-byte aligned.

If int is 4 bytes, this means that for every new int(10) you're getting four bytes and making 12 bytes unusable.

This alone would explain the difference between getting 500MB of usable space from small allocations and 2000MB from large ones.

On top of that, there's overhead of keeping track of allocated blocks (at a minimum, of their size and whether they're free or in use). That is very much specific to your system's memory allocator but also incurs per-allocation overhead. See "What is a Chunk" in https://sourceware.org/glibc/wiki/MallocInternals for an explanation of glibc's allocator.