In the case, the "heap" in question isn't the same as the data structure known as a heap.
Typically "heap" refers to the memory managed by malloc/realloc/free. These are typically used quite rarely (if at all) in reasonably written C++.
For dynamic allocation in C++, you more often use new and delete (at least indirectly, such as via std::allocator<T> being used by a container). Some people sometimes refer to this as the "heap" as well, but people trying to be more proper more often refer to it as the "free store" (that's the phrasing used in the standard).
Either way, however, there's rarely (if ever) an actual heap involved though. Neither specifies (or is intended to refer to) the data structure(s) used to manage the memory.
For what it's worth, the closest thing to an actual heap I've seen used for managing memory is with a "buddy system" allocator (but I've seen relatively few of these in actual use, even though Knuth goes into quite a bit of detail about them.
As to what structures are used, one extremely common structure is just a linked list of blocks. Each block will at least record its own size.
The common elementary algorithms are best-fit, worst-fit and first-fit.
- Best fit means finding the smallest free block large enough to satisfy a request. To do this, you typically keep your list of free blocks sorted in ascending order by size, so the first block that's large enough is also the best fit.
- Worst fit means always starting from the largest block. To do this, you typically keep the list of free blocks sorted in descending order by size. This way, either the first block in the list is the largest so you always either use it, or the allocation fails (or you need to do something like allocation more from the OS). In most cases you still need to do some list traversal though, because you split the largest block into two: the one you're allocating to the user, and the other of what's left, which you then re-insert into the list in order by its new size.
- first fit means you walk through the list and use the first block that can satisfy the allocation.
In all cases, you typically have a policy for block splitting. That is, if an allocation asks for a smaller size than the block you select, you have a choice between leaving that block as it is, and just giving the user a little extra memory, or else splitting that block into two: one that's used to satisfy the allocation, and the other goes back into the free list. In most cases, you try to avoid creating minuscule blocks, so unless the "left over" part is greater than some particular size, you just leave the original block intact.
If they don't think much about things, most people's first instinct is to use best-fit. The problem with best fit is that when you split a block, it produces the smallest left-over piece, so you tend to end up with lots of tiny blocks that can't satisfy any allocations. If you do use it, you typically want to set a fairly high threshold where you'll just keep a block intact instead of splitting it.
Worst fit tries to counteract that. Although it's likely to split the largest block, it tends to leave the largest left over block, so it's the most likely to be usable.
There are also hybrid, such as exact-fit, worst fit. That is, instead of always using the largest block, you first look for a block that fits exactly (or close enough that you wouldn't split that block), and only if that fails, you split the biggest block.
If you're keeping the free blocks in some order, there's also the obvious modification of using a tree of some sort or other to store the blocks, so you can find a block in roughly logarithmic time instead of linear time.
