Как я писал Биномиальную кучу

[knstqq]

std::list<std::shared_ptr> childs;


Для реализации хипа не нужен динамический список на умных указателях, следует использовать плоский массив. Поэтому перформанс получился не очень.

shared_ptr

shared_ptr даёт дополнительное замедление ввиду блокировок внутри, он расчитан на использование в multi-threading окружении. В этой задаче, если уж никак не получается без указателей и динамической памяти (а надо!) — уж лучше unique_ptr использовать, оверхед будет меньше.

Если map хранит всё (насколько мне известно) не на указателях, а подряд, то в моей куче это пока не так (и есть над чем поработать в будущем).

Как раз хранит всё на указателях, там обычно красно-чёрное дерево.
В случае если нужно без указателей обойтись, есть структуры данных `flap_map` (десятки сторонних библиотек).

Если хочется готовую структуру — в С++ есть std::priority_queue (основано на плоском std::vector), который будет в 3-10 раз быстрее и эффективнее по памяти чем это решение или std::map

[encyclopedist]

Помимо std::priority_queue в ситандартной библиотеке есть и более низкоуровневые операции с кучей, на основе которых можно строить и свои абстракции: make_heap, push_heap, pop_heap, sort_heap