Indexed Heap

This package provides a pure-Python implementation of MinHeap and MaxHeap that extend standard heap functionality with support for:

• Efficient removal of any value.
• Removal of multiple occurrences of a value in a single operation.
• Insertion of multiple occurrences of a value in a single operation.
• Tracking frequency to handle duplicate values.
• Iteration in sorted order (ascending for MinHeap, descending for MaxHeap) without modifying the heap.
• Container-like behavior with implementations for len(), in, equality checks, and truthiness.

Features & Time Complexity

Notes:

• Equality checks (heap1 == heap2) are structural and strict. Heaps with identical values but different insertion orders (resulting in different internal layouts) will not be considered equal.
• count refers to the number of occurrences to insert or remove from the heap, defaults to 1.

Installation

pip install indexedheap

Quick Reference

Create an empty heap

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap() # Heap is empty.
max_heap = MaxHeap() # Heap is empty.

Create a heap from a list

from indexedheap import MinHeap, MaxHeap

arr = [1,2,3]
min_heap = MinHeap(arr) # Heap contains: [(value: 1, frequency: 1), (value: 2, frequency: 1), (value: 3, frequency: 1)].
max_heap = MaxHeap(arr) # Heap contains: [(value: 3, frequency: 1), (value: 1, frequency: 1), (value: 2, frequency: 1)].

Insert a value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap() # Heap is empty.
min_heap.insert(1) # Heap contains: [(value: 1, frequency: 1)].

max_heap = MaxHeap() # Heap is empty.
max_heap.insert(1) # Heap contains: [(value: 1, frequency: 1)].

Insert a value multiple times

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap() # Heap is empty.
min_heap.insert(1, count=2) # Heap contains: [(value: 1, frequency: 2)].

max_heap = MaxHeap() # Heap is empty.
max_heap.insert(1, count=2) # Heap contains: [(value: 1, frequency: 2)].

Remove a value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1]) # Heap contains: [(value: 1, frequency: 1)].
min_heap.remove(1) # Heap is empty.

max_heap = MaxHeap([1]) # Heap contains: [(value: 1, frequency: 1)].
max_heap.remove(1) # Heap is empty.

Remove multiple occurrences of a value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
min_heap.remove(1, count=2) # Heap is empty.

max_heap = MaxHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
max_heap.remove(1, count=2) # Heap is empty.

Remove all occurrences of a value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
min_heap.remove(1, count=min_heap.count(1)) # Heap is empty.

max_heap = MaxHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
max_heap.remove(1, count=max_heap.count(1)) # Heap is empty.

Optimistically remove a value

The strict flag controls whether removing a non-existent value should raise an error:

• strict=True (default) -> raise a KeyError if the value isn't in the heap
• strict=False -> attempt to remove the value (up to the given count, if provided), but do nothing if it isn't present

from indexedheap import MinHeap, MaxHeap

# Value not present — no error
min_heap = MinHeap([]) # Heap is empty.
min_heap.remove(1) # Raises KeyError.
min_heap.remove(1, strict=False) # Heap is empty, no error.

# Value present, but count exceeds frequency — no error
min_heap = MinHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
min_heap.remove(1, count=3) # Raises ValueError.
min_heap.remove(1, count=3, strict=False) # Heap is empty, no error.

# Same for MaxHeap
max_heap = MaxHeap([]) # Heap is empty.
max_heap.remove(1) # Raises KeyError.
max_heap.remove(1, strict=False) # Heap is empty, no error.

max_heap = MaxHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
max_heap.remove(1, count=3) # Raises ValueError.
max_heap.remove(1, count=3, strict=False) # Heap is empty, no error.

Peek root value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 2]) # Heap contains: [(value: 1, frequency: 1), (value: 2, frequency: 1)].
min_heap.peek() # Returns 1; Heap unchanged.

max_heap = MaxHeap([1, 2]) # Heap contains: [(value: 2, frequency: 1), (value: 1, frequency: 1)].
max_heap.peek() # Returns 2; Heap unchanged.

Pop root value

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 2]) # Heap contains: [(value: 1, frequency: 1), (value: 2, frequency: 1)].
min_heap.pop() # Returns 1; Heap contains: [(value: 2, frequency: 1)].

max_heap = MaxHeap([1, 2]) # Heap contains: [(value: 2, frequency: 1), (value: 1, frequency: 1)].
max_heap.pop() # Returns 2; Heap contains: [(value: 1, frequency: 1)].

Get frequency (count) of value

from indexedheap import MinHeap, MaxHeap

# Value present
min_heap = MinHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
min_heap.count(1) # Returns 2; Heap unchanged.

max_heap = MaxHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
max_heap.count(1) # Returns 2; Heap unchanged.

# Value not present
min_heap = MinHeap() # Heap is empty.
min_heap.count(1) # Returns 0; Heap unchanged.

max_heap = MaxHeap() # Heap is empty.
max_heap.count(1) # Returns 0; Heap unchanged.

Get heap size (including duplicates)

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
len(min_heap) # Returns 2; Heap unchanged.

min_heap = MinHeap([1, 2]) # Heap contains: [(value: 1, frequency: 1), (value: 2, frequency: 1)].
len(min_heap) # Returns 2; Heap unchanged.

max_heap = MaxHeap([1, 1]) # Heap contains: [(value: 1, frequency: 2)].
len(max_heap) # Returns 2; Heap unchanged.

max_heap = MaxHeap([1, 2]) # Heap contains: [(value: 2, frequency: 1), (value: 1, frequency: 1)].
len(max_heap) # Returns 2; Heap unchanged.

Iterate heap contents in sorted order

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 3, 2]) # Heap contains: [(value: 1, frequency: 1), (value: 3, frequency: 1), (value: 2, frequency: 1)].
for value in min_heap:
    print(value)
# >>> 1
# >>> 2
# >>> 3
# Iteration yields values in sorted order; Heap unchanged.

max_heap = MaxHeap([1, 3, 2]) # Heap contains: [(value: 3, frequency: 1), (value: 1, frequency: 1), (value: 2, frequency: 1)].
for value in max_heap:
    print(value)
# >>> 3
# >>> 2
# >>> 1
# Iteration yields values in sorted order; Heap unchanged.

Get heap contents as a sorted list

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1, 3, 2]) # Heap contains: [(value: 1, frequency: 1), (value: 3, frequency: 1), (value: 2, frequency: 1)].
min_heap.to_sorted_list() # Returns [1, 2, 3]; Heap unchanged.

max_heap = MaxHeap([1, 3, 2]) # Heap contains: [(value: 3, frequency: 1), (value: 1, frequency: 1), (value: 2, frequency: 1)].
max_heap.to_sorted_list() # Returns [3, 2, 1]; Heap unchanged.

# list(heap) also returns items in sorted order because __iter__ yields items sorted.
list(min_heap)  # Returns [1, 2, 3]; Heap unchanged.
list(max_heap)  # Returns [3, 2, 1]; Heap unchanged.

Test Membership

from indexedheap import MinHeap, MaxHeap

min_heap = MinHeap([1]) # Heap contains: [(value: 1, frequency: 1)].
1 in min_heap # Returns True.
0 in min_heap # Returns False.

max_heap = MaxHeap([1]) # Heap contains: [(value: 1, frequency: 1)].
1 in max_heap # Returns True.
0 in max_heap # Returns False.