Skip to main content

​
BoundedHeap

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

​
BoundedHeap

inline
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
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
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
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
Get current number of elements in heap.

​
Returns

Number of elements (0 to limit_)

​
empty

const
Check if heap is empty.

​
Public Types

​
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

​
data_

Internal heap storage.

​
limit_

Maximum capacity.

​
dist_

Distance evaluation function.

​
Private Methods

​
sift_up

inline
Restore heap property by moving element up.

​
sift_down

inline
Restore heap property by moving element down.