Skip to main content

​
BoundedHeap

#include <heap.hpp>
Bounded heap for top-K element selection. A priority queue that maintains a fixed maximum size. When capacity is reached, new elements only replace the worst element if they are better (have lower distance according to the provided function).

​
Parameters

  • T Type of elements stored in the heap
limit_ >= 1 dist_ must not throw or mutate state :::note Provides O(log n) insert and O(1) peek ::: :::note Memory: O(limit_) elements maximum :::

​
Public Methods

ReturnNameDescription
BoundedHeapConstruct a bounded heap.
voidinsertInsert an element into the heap.
const T *peek constPeek at the worst (highest-distance) element in the heap.
std::vector< T >to_sorted constExtract all elements sorted by distance.
std::size_tsize constGet current number of elements in heap.
boolempty constCheck if heap is empty.

​
BoundedHeap

inline 
inline BoundedHeap(std::size_t limit, DistFn dist)
Construct a bounded heap.

​
Parameters

  • limit Maximum number of elements to retain
  • dist Distance function - lower values are preferred

​
Exceptions

  • std::invalid_argument If limit < 1
Heap is empty and ready for inserts

​
insert

inline 
inline void insert(T entry)
Insert an element into the heap. If heap is not full, adds element. If heap is full, only adds element if it is better than the current worst (root).

​
Parameters

  • entry Element to insert
If heap was not full, element is in heap If heap was full and entry is better than root, root is replaced Heap property is maintained after insert

​
peek

const 
inline const T * peek() const
Peek at the worst (highest-distance) element in the heap.

​
Returns

Pointer to root element (max distance), or nullptr if empty :::note The returned pointer is invalid after insert() or destruction :::

​
to_sorted

const 
inline std::vector< T > to_sorted() const
Extract all elements sorted by distance.

​
Returns

Vector of elements sorted from best to worst :::note Returns copy of elements; original heap is unchanged :::

​
size

const 
inline std::size_t size() const
Get current number of elements in heap.

​
Returns

Number of elements (0 to limit_)

​
empty

const 
inline bool empty() const
Check if heap is empty.

​
Public Types

NameDescription
DistFnDistance function type.

​
DistFn

std::function< double(const T &)> DistFn()
Distance function type. Takes a reference to an element and returns a distance value. Lower values are considered “better” (closer to target).

​
Private Attributes

ReturnNameDescription
std::vector< T >data_Internal heap storage.
std::size_tlimit_Maximum capacity.
DistFndist_Distance evaluation function.

​
data_

std::vector< T > data_
Internal heap storage.

​
limit_

std::size_t limit_
Maximum capacity.

​
dist_

DistFn dist_
Distance evaluation function.

​
Private Methods

ReturnNameDescription
voidsift_upRestore heap property by moving element up.
voidsift_downRestore heap property by moving element down.

​
sift_up

inline 
inline void sift_up(std::size_t i)
Restore heap property by moving element up.

​
sift_down

inline 
inline void sift_down(std::size_t i)
Restore heap property by moving element down.