jpt.base.utils.heap

Classes

Heap	Min-heap with a custom key function and stable insertion-order tiebreaking.

Functions

_count([start, inc])

Module Contents

jpt.base.utils.heap._count(start: int = 0, inc: int = 1)

class jpt.base.utils.heap.Heap(data: Iterable[Any] = None, key: Callable = None, inc: int = 1)

Min-heap with a custom key function and stable insertion-order tiebreaking.

Elements are stored as (key(item), insertion_index, item) triples so that heapq never needs to compare item objects directly. The inc parameter controls how insertion indices advance:

• inc=1 (default) — older elements have smaller indices and are therefore popped first when keys are equal (FIFO tiebreaking).

• inc=-1 — newer elements have smaller indices and are therefore popped first when keys are equal (LIFO tiebreaking).

The public interface mirrors collections.deque where it makes sense: pop() / popleft() remove the minimum, while popright() removes the element at the tail of the internal array (useful for lazy-deletion patterns, but does not guarantee maximum).

Example:

>>> h = Heap(data=[5, 1, 3])
>>> h.pop()
1
>>> h.push(0)
>>> list(h)
[0, 3, 5]

Initialise the heap.

Parameters:

• data – Optional iterable of initial elements. All items are inserted at once and the heap is built in O(n) time via heapq.heapify().

• key – A one-argument callable used to derive the sort key from each item. Defaults to the identity function so that items are compared directly.

• inc – Increment applied to the internal insertion counter after each push(). Use 1 for FIFO tiebreaking (default) and -1 for LIFO tiebreaking.

class Iterator(heap: Heap, reverse: bool = False)

Forward or reverse iterator over the items in heap storage order.

Iterates the underlying _data list directly — i.e. in heap-array order, not in sorted order — without disturbing the heap.

Parameters:

• heap – The Heap to iterate.

• reverse – If True, iterate from the tail to the head of the internal array.

heap

_list_iterator

__next__()

__iter__()

_key

_index = 0

_inc = 1

push(item: Any) → None

Push item onto the heap.

Parameters:

item – The element to add. Its sort key is computed via the key function supplied at construction time.

pop() → Any

Remove and return the smallest element.

Raises:

IndexError – If the heap is empty.

popleft() → Any

Alias for pop() — remove and return the smallest element.

Provided for API symmetry with collections.deque.

Raises:

IndexError – If the heap is empty.

popright() → Any

Remove and return the element at the tail of the internal array.

Warning

This is not guaranteed to return the maximum element. In a min-heap the tail of the backing array is a leaf node, which can hold any value. This method is intended for lazy-deletion: locate an item with index(), then remove it with del heap[idx] or swap-and-popright.

Raises:

IndexError – If the heap is empty.

index(item: Any) → int

Return the position of item in the internal storage array.

Uses identity comparison (==). When multiple equal items exist the index of the first match in array order is returned.

Parameters:

item – The element to search for.

Returns:

Zero-based index into the backing array.

Raises:

ValueError – If item is not present.

__len__() → int

Return the number of elements in the heap.

__getitem__(item: int) → Any

Return the element stored at raw array index item.

Index 0 always holds the minimum element (heap invariant).

Parameters:

item – Zero-based index into the backing array.

Raises:

IndexError – If item is out of range.

__delitem__(item: int) → None

Delete the element at raw array index item.

Note

Removing an element other than the root breaks the heap invariant. The backing array is mutated directly without re-heapifying. Prefer pop() for ordinary removal; use this only when you hold a valid index from index() and accept the invariant violation (e.g. inside a rebuild loop).

Parameters:

item – Zero-based index into the backing array.

Raises:

IndexError – If item is out of range.

__bool__() → bool

Return True if the heap contains at least one element.

__repr__() → str

__iter__() → Heap

Return a forward iterator over items in backing-array order.

__reversed__() → Heap

Return a reverse iterator over items in backing-array order.