clustering::IndexedHeap< Key, Val, Idx > Class Template Reference

Binary min-heap keyed on Key with O(1) handle-to-position lookup. More...

#include <clustering/math/heap.h>

Classes
struct	Entry
	One heap entry. More...

Public Member Functions
	IndexedHeap (std::size_t capacity)
	Construct an empty heap capable of handles in [0, capacity).
void	push (Idx handle, Key key, Val val)
	Insert an entry for handle.
bool	contains (Idx handle) const noexcept
	Whether handle is currently present in the heap.
void	decreaseKey (Idx handle, Key newKey) noexcept
	Lower the key of handle's entry to newKey.
const Entry &	top () const noexcept
	Smallest-key entry currently in the heap.
Entry	pop () noexcept
	Remove and return the smallest-key entry.
std::size_t	size () const noexcept
	Current number of entries.
bool	empty () const noexcept
	Whether the heap holds zero entries.
std::size_t	capacity () const noexcept
	Maximum handle + 1 (the capacity passed at construction).

Static Public Attributes
static constexpr std::size_t	kNotInHeap = std::numeric_limits<std::size_t>::max()
	Sentinel for "handle not currently in the heap". Equal to size_t's max.

Detailed Description

template<class Key, class Val, class Idx = std::uint32_t>
class clustering::IndexedHeap< Key, Val, Idx >

Binary min-heap keyed on Key with O(1) handle-to-position lookup.

Each heap entry carries an external Idx handle drawn from a fixed range [0, capacity). At most one entry per handle is in the heap at any time; the handle is cleared on pop and on construction. decreaseKey looks up the handle's position through m_posMap and sifts up; O(log n) worst case. Backed by heap-allocated vectors; allocation is constrained to construction and the occasional m_heap growth, never inside push / pop / decreaseKey.

Template Parameters

Key	Orderable key type; smaller keys pop first.
Val	Payload carried alongside the key.
Idx	Unsigned integer handle type; defaults to uint32_t. Handles index into a capacity-sized position map.

Definition at line 109 of file heap.h.

Constructor & Destructor Documentation

IndexedHeap()

template<class Key, class Val, class Idx = std::uint32_t>

clustering::IndexedHeap< Key, Val, Idx >::IndexedHeap ( std::size_t capacity )

inlineexplicit

Construct an empty heap capable of handles in [0, capacity).

Allocates the position map to capacity entries filled with kNotInHeap.

Parameters

capacity

Upper bound on handle values.

Definition at line 137 of file heap.h.

Member Function Documentation

capacity()

template<class Key, class Val, class Idx = std::uint32_t>

std::size_t clustering::IndexedHeap< Key, Val, Idx >::capacity ( ) const

inlinenodiscardnoexcept

Maximum handle + 1 (the capacity passed at construction).

Returns

Size of the internal position map.

Definition at line 245 of file heap.h.

contains()

template<class Key, class Val, class Idx = std::uint32_t>

bool clustering::IndexedHeap< Key, Val, Idx >::contains ( Idx handle ) const

inlinenodiscardnoexcept

Whether handle is currently present in the heap.

Parameters

handle

Handle to query; must be less than capacity.

Returns

true iff an entry for handle is present.

Definition at line 165 of file heap.h.

decreaseKey()

template<class Key, class Val, class Idx = std::uint32_t>

void clustering::IndexedHeap< Key, Val, Idx >::decreaseKey ( Idx handle, Key newKey )

inlinenoexcept

Lower the key of handle's entry to newKey.

Asserts handle is present and newKey is not greater than the current key (the classic decreaseKey precondition – raising a key would require sifting down, a different path). Sifts up from the handle's position; O(log n).

Parameters

handle	Handle of the entry to update.
newKey	Replacement key; must satisfy newKey <= current key.

Definition at line 181 of file heap.h.

empty()

template<class Key, class Val, class Idx = std::uint32_t>

bool clustering::IndexedHeap< Key, Val, Idx >::empty ( ) const

inlinenodiscardnoexcept

Whether the heap holds zero entries.

Returns

true iff size() == 0.

Definition at line 238 of file heap.h.

pop()

template<class Key, class Val, class Idx = std::uint32_t>

Entry clustering::IndexedHeap< Key, Val, Idx >::pop ( )

inlinenoexcept

Remove and return the smallest-key entry.

Clears the popped handle's slot in m_posMap; the handle becomes contains(h) == false.

Returns

The popped Entry by value.

Definition at line 210 of file heap.h.

push()

template<class Key, class Val, class Idx = std::uint32_t>

void clustering::IndexedHeap< Key, Val, Idx >::push ( Idx handle, Key key, Val val )

inline

Insert an entry for handle.

Asserts handle is in range and not already present. Sifts up to restore the heap invariant; O(log n).

Parameters

handle	External identity of the entry; must be less than capacity.
key	Ordering key.
val	Payload.

Definition at line 149 of file heap.h.

size()

template<class Key, class Val, class Idx = std::uint32_t>

std::size_t clustering::IndexedHeap< Key, Val, Idx >::size ( ) const

inlinenodiscardnoexcept

Current number of entries.

Returns

Entry count.

Definition at line 231 of file heap.h.

top()

template<class Key, class Val, class Idx = std::uint32_t>

const Entry & clustering::IndexedHeap< Key, Val, Idx >::top ( ) const

inlinenodiscardnoexcept

Smallest-key entry currently in the heap.

Asserts on an empty heap.

Returns

Const reference to the top entry.

Definition at line 198 of file heap.h.

Member Data Documentation

kNotInHeap

template<class Key, class Val, class Idx = std::uint32_t>

std::size_t clustering::IndexedHeap< Key, Val, Idx >::kNotInHeap = std::numeric_limits<std::size_t>::max()

staticconstexpr

Sentinel for "handle not currently in the heap". Equal to size_t's max.

Definition at line 114 of file heap.h.

---

The documentation for this class was generated from the following file:

• include/clustering/math/heap.h