clustering::BinaryHeap< Key, Val > Class Template Reference

Binary min-heap of (key, val) pairs ordered on key. More...

#include <clustering/math/heap.h>

Public Member Functions
	BinaryHeap ()=default
void	push (Key key, Val val)
	Insert a new (key, val) entry.
const std::pair< Key, Val > &	top () const noexcept
	Smallest-key entry currently in the heap.
void	pop () noexcept
	Remove the smallest-key entry.
std::size_t	size () const noexcept
	Current number of entries.
bool	empty () const noexcept
	Whether the heap holds zero entries.

Detailed Description

template<class Key, class Val>
class clustering::BinaryHeap< Key, Val >

Binary min-heap of (key, val) pairs ordered on key.

Plain d=2 heap backed by a single std::vector. push, top, pop are the full surface; no bulk-build, no merge, no handles. Use IndexedHeap when a stable handle and decreaseKey are needed.

Template Parameters

Key	Orderable key type; operator< defines the ordering. Smaller keys pop first.
Val	Payload carried alongside the key.

Definition at line 25 of file heap.h.

Constructor & Destructor Documentation

BinaryHeap()

template<class Key, class Val>

clustering::BinaryHeap< Key, Val >::BinaryHeap ( )

default

Member Function Documentation

empty()

template<class Key, class Val>

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

inlinenodiscardnoexcept

Whether the heap holds zero entries.

Returns

true iff size() == 0.

Definition at line 84 of file heap.h.

pop()

template<class Key, class Val>

void clustering::BinaryHeap< Key, Val >::pop ( )

inlinenoexcept

Remove the smallest-key entry.

Swaps the root with the tail, pops the tail, then sifts the new root down. O(log n). Asserts on an empty heap.

Definition at line 60 of file heap.h.

push()

template<class Key, class Val>

void clustering::BinaryHeap< Key, Val >::push ( Key key, Val val )

inline

Insert a new (key, val) entry.

Appends at the tail and sifts up to restore the heap invariant; O(log n).

Parameters

key	Ordering key.
val	Payload.

Definition at line 37 of file heap.h.

size()

template<class Key, class Val>

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

inlinenodiscardnoexcept

Current number of entries.

Returns

Entry count.

Definition at line 77 of file heap.h.

top()

template<class Key, class Val>

const std::pair< Key, Val > & clustering::BinaryHeap< Key, Val >::top ( ) const

inlinenodiscardnoexcept

Smallest-key entry currently in the heap.

Asserts on an empty heap – the caller must guard with empty.

Returns

Const reference to the top (key, val) pair.

Definition at line 49 of file heap.h.

---

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

• include/clustering/math/heap.h