C++ Heap Overview

Binary heap handling in C++ is traditionally performed with std::priority_queue. While this standard container provides convenient priority-ordered access, it wraps std::deque or std::vector with an allocator interface that is opaque and not well suited to deterministic, embedded, real-time, or safety-regulated environments. In such systems, explicit control over memory placement, allocation strategy, and failure behavior is often more important than full generality.

The C++ Heap module in this library provides a lightweight, allocator-aware generic binary heap container implemented in C++ and declared in array.hpp. Unlike std::priority_queue, this container:

• Integrates directly with custom allocator hierarchies

• Delegates all element storage and tiered growth to Array<T>

• Fixes the element type and comparator at compile time via template parameters

• Enforces initialization through a factory pattern preventing invalid state

• Provides automatic cleanup via RAII with custom deleters

• Returns explicit success/error state using the Expected<T> pattern

• Supports push, pop, peek, copy, and templated iteration via foreach()

The heap is implemented on top of cslt::Array<T>, which means all growth strategy, buffer management, and element lifetime handling are inherited directly. Changes to Array<T>'s growth policy automatically apply to Heap<T, Compare> without any duplication.

The only dependencies this module has within the CSalt library are the array.hpp, allocator.hpp, and error.hpp files, keeping the container self-contained and suitable for use in larger systems with minimal coupling.

Comparator Convention

The template parameter Compare determines heap ordering. It must be a callable with signature bool(const T&, const T&) that returns true when its first argument has higher priority than its second. This convention matches std::priority_queue and the standard library comparator types:

Comparator	Heap type
std::less<T>	Max-heap — largest element at root
std::greater<T>	Min-heap — smallest element at root
Lambda / custom functor	Any total ordering

For std::less<T> and std::greater<T> to work, T must define operator<. When a lambda or custom functor is used, the element type needs no comparison operators at all — the ordering logic is provided entirely by the comparator.

// Max-heap of integers — largest value at root
cslt::Heap<int, std::less<int>>;

// Min-heap of integers — smallest value at root
cslt::Heap<int, std::greater<int>>;

// Custom struct heap ordered by a field — T needs no operator<
struct Particle { float mass; float charge; };
auto cmp = [](const Particle& a, const Particle& b) {
    return a.mass < b.mass;   // max-heap by mass
};
cslt::Heap<Particle, decltype(cmp)>::init(16, true, alloc, cmp);

Allocator Integration

By integrating directly with the Allocator base class defined in allocator.hpp, the heap container supports multiple allocation strategies without changing the public API. The heap allocates:

• the Heap<T, Compare> object itself

• the backing Array<T> and its element buffer, through the same allocator

This makes the container compatible with the following allocator strategies:

• HeapAllocator — Best general-purpose choice for testing and normal host-side use

• ArenaAllocator — Useful when the heap has bulk lifetime semantics and is destroyed all at once

• BuddyAllocator — Useful when deterministic block allocation and returnable memory are important

• PoolAllocator — Suitable for small heaps with a bounded element count

• SlabAllocator — Appropriate when the element type is fixed-size and uniform

• Custom allocators — Any user-defined class inheriting from Allocator

Because the heap delegates to Array<T> for storage, the allocator is used for both the initial element buffer and any subsequent growth. The allocator therefore has direct influence over:

• where the heap object itself lives

• where the element buffer lives

• whether growth allocations succeed or fail deterministically

Recommended Allocators

Different allocators are appropriate depending on how the heap is used:

• HeapAllocator

  Best for:

  • general-purpose use

  • unit testing

  • host-side applications

  • debugging heap logic independent of allocator complexity

  This is usually the best allocator to start with because failure modes are simple and easy to reason about.

• ArenaAllocator

  Best for:

  • build-then-query workflows

  • heaps used transiently during scheduling or sorting passes

  • scenarios where the full heap lifetime matches a larger arena lifetime

  Works well when the heap size is bounded and growth is rare. If the heap grows frequently, the arena must have sufficient capacity.

• BuddyAllocator

  Best for:

  • deterministic dynamic allocation

  • environments where memory should be returnable and coalesced after use

  • systems requiring more structure than a raw heap allocator

  A reasonable choice when the heap may grow and the buffer should be returneable on destruction.

• PoolAllocator / SlabAllocator

  Best for:

  • fixed-capacity heaps with a known maximum element count

  • performance-sensitive paths with many push/pop operations

  • safety-regulated environments where growth must be prevented

  These allocators pair well with growth = false in init(), producing a bounded-capacity heap with fully deterministic allocation behavior.

Factory Pattern and RAII

Unlike direct constructor-based creation, heap creation uses a static factory function Heap::init() that returns Expected<Heap<T, Compare>*>. This design:

• Prevents creation of partially initialized heaps

• Ensures the backing array and heap struct are allocated through the chosen allocator

• Provides explicit error handling at the point of creation

• Returns typed error objects such as ArgumentError and MemoryError

Memory cleanup is automatic through the HeapDeleter custom deleter, which works with UniquePtr to provide RAII semantics. The deleter calls ArrayDeleter<T> on the backing array before freeing the heap struct, ensuring all elements are correctly destroyed and all memory is returned to the allocator in the right order:

{
    cslt::HeapAllocator allocator;
    auto result = cslt::Heap<int, std::less<int>>::init(8, true, allocator);
    if (result.hasValue()) {
        cslt::UniquePtr<cslt::Heap<int, std::less<int>>,
                        cslt::HeapDeleter<int, std::less<int>>> h(result.value());
        h->push(5);
        h->push(3);
        h->push(7);
    } // heap and backing buffer automatically freed here
}

Backing Storage

The heap stores its elements in a contiguous Array<T> buffer using the standard binary heap array encoding:

• the root is at index 0

• the children of node at index i are at indices 2i + 1 and 2i + 2

• the parent of node at index i is at index (i - 1) / 2

This layout means the entire heap is stored in a single contiguous allocation, which provides good cache behaviour during sift operations. The sift helpers access Array::data_ directly through a C++ friendship declaration, bypassing the Expected<T>-returning public API to avoid overhead in tight sift loops.

When growth is enabled the buffer expands using Array's tiered growth strategy:

Current capacity	New capacity
0 elements	1
< 1,024 elements	2× current
< 8,192 elements	1.5× current (cap + cap/2)
< 65,536 elements	1.25× current (cap + cap/4)
≥ 65,536 elements	current + 256 (linear increment)

When growth is disabled, push() returns false once the buffer is full, giving the caller full control over the maximum memory footprint.

Heap Property

The heap maintains the invariant that for every element at index i, Compare()(element[i], element[child]) is true for all children of i. This means the root always has the highest priority element under the stored comparator.

Two internal operations maintain this invariant:

• Sift-up — called after push(). The new element is appended to the end of the backing array and bubbled upward by repeatedly swapping with its parent until the comparator is satisfied.

• Sift-down — called after pop(). The last element is moved to the root and pushed downward by repeatedly swapping with the higher-priority child until the comparator is satisfied at every level.

The swap operation uses memcpy for trivially copyable T and move-construction with explicit destructor calls for non-trivial T, consistent with the strategy used in Array<T>.

Element Type Requirements

The Heap<T, Compare> container supports any element type T that is:

• default-constructible (required by Expected<T>, which is returned by pop() and peek())

• copy-constructible (elements are copied into the buffer on push())

• destructible (elements are destroyed explicitly during sift swaps and on pop() and destruction)

The comparator type Compare must be:

• default-constructible (used when cmp is omitted from init())

• callable as bool(const T&, const T&)

Requirement	Reason
T default-constructible	Expected<T> default constructor
T copy-constructible	Placement-new into backing buffer on push
T destructible	Explicit destructor calls during sift and pop
Compare default-ctible	Default cmp argument in init()
Compare callable	Used in _sift_up and _sift_down

Ordered Traversal

The foreach() method visits elements in backing-array (heap-internal) order, which satisfies the heap property but is not sorted order. If ordered traversal is required, copy the heap and pop from the copy in a loop:

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::less<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::less<int>>,
                cslt::HeapDeleter<int, std::less<int>>> h(r.value());

h->push(5);
h->push(3);
h->push(7);
h->push(1);

// Ordered traversal — copy the heap, then pop from the copy
auto cr = cslt::Heap<int, std::less<int>>::copy(*h, alloc);
if (!cr.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::less<int>>,
                cslt::HeapDeleter<int, std::less<int>>> tmp(cr.value());

while (!tmp->is_empty()) {
    auto pr = tmp->pop();
    if (pr.hasValue()) {
        // elements visited in descending order: 7, 5, 3, 1
    }
}
// h is unchanged — still contains all 4 elements

Use Cases

This heap implementation is particularly useful in the following scenarios:

• priority queues for task scheduling in embedded or real-time systems

• Dijkstra's algorithm and other graph searches requiring a priority queue

• event-driven simulations ordered by event timestamp

• top-K selection from a large dataset without full sorting

• stream processing where only the current minimum or maximum is needed

• any workload requiring O(log n) insert and O(log n) remove-root

When elements need to be accessed by index or sorted in place, Array<T> with its sort() method is usually the better choice. When the priority of the next element to process must always be available in O(1) and insertions arrive dynamically, the heap is the right container.

Heap Class

template<typename T, typename Compare>
class Heap

Allocator-backed generic binary heap backed by cslt::Array<T>.

Implements a binary heap whose element storage, capacity management, and tiered growth strategy are provided entirely by an owned cslt::Array<T> instance. The Heap class itself is responsible only for maintaining the heap property via sift-up and sift-down operations, and for managing the comparator.

The template parameter Compare determines heap ordering. It must be a callable with signature bool(const T&, const T&) that returns true when its first argument has higher priority than its second:

// Min-heap — smallest element at root
cslt::Heap<int, std::greater<int>> min_heap;

// Max-heap — largest element at root
cslt::Heap<int, std::less<int>> max_heap;

// Lambda comparator — custom priority
auto cmp = [](const Task& a, const Task& b){ return a.priority > b.priority; };
cslt::Heap<Task, decltype(cmp)> task_heap;

Key features:

• All storage, growth, and element lifetime delegated to Array<T>

• No duplicated growth logic — changes to Array<T> growth strategy automatically apply to Heap<T, Compare>

• Template parameters T and Compare fix element type and ordering at compile time — no runtime type tags or function pointer casts

• Factory pattern via init() prevents uninitialised instances

• RAII cleanup through HeapDeleter and UniquePtr

• Returns explicit success/error state using the Expected<T> pattern

• foreach() iteration accepts any callable with signature void(const T&)

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(16, true, alloc);
if (r.hasValue()) {
    cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                    cslt::HeapDeleter<int, std::greater<int>>> h(r.value());
    h->push(5);
    h->push(1);
    h->push(3);
    auto pr = h->pop();   // Expected<int> containing 1  (min-heap)
}

Template Parameters:

• T – Element type. Must be default-constructible, copy-constructible, and destructible. Default-constructibility is required by Expected<T>.

• Compare – Comparator type. Must be default-constructible and callable as bool(const T&, const T&). Returns true when the first argument has higher priority than the second.

Public Functions

inline bool push(const T &value) noexcept

Insert an element into the heap and restore the heap property.

Delegates the actual insertion and any required growth to Array::push_back(), then sifts the new element upward.

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> h(r.value());

h->push(5);
h->push(1);   // root becomes 1 (min-heap)
h->push(3);
// h->peek().value() == 1

Parameters:

value – Element to copy into the heap

Returns:

true on success; false if the backing array is full and growth is disabled, or if allocation fails

inline Expected<T> pop() noexcept

Remove the root (highest-priority) element and return its value.

Copies the root value, moves the last element into the root slot via Array’s internal buffer, decrements the array length, then sifts downward to restore the heap property.

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> h(r.value());

h->push(5);
h->push(1);
h->push(3);

auto pr = h->pop();
if (pr.hasValue()) {
    int v = pr.value();   // v == 1 (min-heap root)
}

Returns:

Expected<T> containing the root value on success, or an EmptyError if the heap contains no elements

inline Expected<T> peek() const noexcept

Return a copy of the root (highest-priority) element.

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> h(r.value());

h->push(5);
h->push(1);
h->push(3);

auto pr = h->peek();
if (pr.hasValue()) {
    int root = pr.value();   // root == 1 (min-heap)
    // h->size() still == 3 — peek does not remove the element
}

Returns:

Expected<T> containing a copy of the root value, or an EmptyError if the heap is empty

template<typename Func>
inline bool foreach(Func fn) const noexcept

Call fn once for every element in heap-internal order.

Traversal is in backing-array order, which satisfies the heap property but is NOT sorted order. Do not rely on elements being visited highest-priority first. For ordered traversal, copy the heap and pop from the copy in a loop.

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> h(r.value());

h->push(5);
h->push(1);
h->push(3);

int total = 0;
h->foreach([&total](const int& v) { total += v; });
// total == 9  (visit order is unspecified beyond heap property)

Template Parameters:

Func – Callable with signature void(const T&). Lambdas, functors, and function pointers are accepted. The callback must not call push() or pop() during traversal.

Parameters:

fn – Callback invoked for each element

Returns:

true on success; false if the heap is uninitialised or empty

inline size_t size() const noexcept

Number of elements currently stored in the heap.

Delegates directly to the backing array.

inline size_t capacity() const noexcept

Allocated capacity in elements.

Delegates directly to the backing array.

inline bool is_empty() const noexcept

true if no elements are stored

inline bool is_full() const noexcept

true if the heap is at full capacity and growth is disabled

Public Static Functions

static inline Expected<Heap<T, Compare>*> init(size_t capacity, bool growth, Allocator &allocator, Compare cmp = Compare{}) noexcept

Allocate and initialise a new Heap.

// Min-heap of integers (smallest value at root)
cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(16, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> h(r.value());

h->push(5);
h->push(1);
h->push(3);
// h->peek().value() == 1  (smallest element is at the root)

Error conditions

• capacity == 0 (ArgumentError, propagated from Array::init)

• Allocation of the backing Array fails (MemoryError)

• Allocation of the Heap struct fails (MemoryError)

Parameters:

• capacity – Initial element capacity passed to Array<T>::init(). Must be > 0.

• growth – Forwarded to Array<T>::init(). If true, the backing array grows automatically when full using Array’s tiered strategy. If false, push() returns false when the array is at capacity.

• allocator – Allocator for the Heap struct and, via Array, the backing element buffer.

• cmp – Comparator instance (default-constructed if omitted). Returns true when its first argument has higher priority than its second.

Returns:

Expected<Heap<T,Compare>*> on success, or an ArgumentError / MemoryError on failure

static inline Expected<Heap<T, Compare>*> copy(const Heap<T, Compare> &src, Allocator &allocator) noexcept

Create a deep copy of src using a caller-supplied allocator.

cslt::HeapAllocator alloc;
auto r = cslt::Heap<int, std::greater<int>>::init(8, true, alloc);
if (!r.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> src(r.value());
src->push(3);
src->push(1);
src->push(2);

// Deep copy — src and dst are fully independent
auto cr = cslt::Heap<int, std::greater<int>>::copy(*src, alloc);
if (!cr.hasValue()) return;
cslt::UniquePtr<cslt::Heap<int, std::greater<int>>,
                cslt::HeapDeleter<int, std::greater<int>>> dst(cr.value());

Parameters:

• src – Heap to copy from

• allocator – Allocator for the new Heap and its backing array

Returns:

Expected<Heap<T,Compare>*> on success, or an error

static inline Expected<Heap<T, Compare>*> copy(const Heap<T, Compare> &src) noexcept

Create a deep copy using the source heap’s own allocator.

auto cr = cslt::Heap<int, std::greater<int>>::copy(*src);

Parameters:

src – Heap to copy from

Returns:

Expected<Heap<T,Compare>*> on success, or an error