Реализация кучи

Если что то называется кучей, это ещё не значит, что оно может быть биномиальной или бинарной кучей. Это может быть куча мусора.

Обычно это все устроено так. Приложение запрашивает у операционной системы большой кусок памяти, а потом уже встроенный менеджер памяти (который реализуется внутри stl/glibc/CRT), нарезает ее мелкими порциями. О большинства операционных систем сложно попросить ровно 2-4 байта памяти. Они обычно меньше 4-16 кб даже не выделяют.

На самом низком уровне в линуксе приложение не может попросить "ось, дай мне метр памяти". Там есть только специальный вызов brk, который подвигает верхнюю границу памяти для процесса. То есть, у процесса есть область памяти с фиксированным началом и он может подвигать верхнюю границу. Что будет делать приложение с памятью в этой области - личное дело приложения. Хотя ещё есть mmap, но это уже отдельная тема.

В Windows есть Heap который достаточно похож на обычный malloc/free.

Какая из них используется?

Самое смешное, что куча для памяти обычно реализуется на базе связанного списка. Можно изучить код с сайта IBM, что бы понять, как устроен malloc/free.

Если хочется понять глубже как это устроено, то можно поизучать различные реализации менеджеров памяти

• tmalloc
• jemalloc

Можно на хабре почитать.

P.S.

Если с реализаций стека всё вроде бы понятно

боюсь, что нет:)