Indexed-Heap

A small Python code implementing an indexed min-heap that maintains a mapping between heap nodes and positions in a "main" array. I think it can be useful for some algorithms that needs indexed updates on heap (replace-by-index) to modify values by their original array index.

Features

• Add (value, main_index)
• Replace value by main_index
• Fast heapify-up/down with mapping maintenance

Example: sliding-window maximum

Even though this solution is not better than original deque solution, it is a practical example of an Indexed Heap

from indexed_heap import IndexedHeap

def maxSlidingWindowHeapSolution(nums: List[int], k: int) -> List[int]:
    """
    Solves the Sliding Window Maximum problem using the IndexedHeap.
    Time Complexity: O(n log k)
    """
    if not nums or k == 0:
        return []
        
    results = []
    heap = IndexedHeap()
    
    for i, num in enumerate(nums):
        # If the window is full, replace the element that is sliding out
        if i >= k:
            # Use the .update() method
            heap.update(
                old_original_index=i - k,
                new_original_index=i,
                new_value=-num
            )
        else:
            # Otherwise, just add elements to fill the initial window
            heap.add(-num, i)
        
        # Once the first full window is formed, start recording the max
        if i >= k - 1:
            min_val, _ = heap.peek()
            results.append(-min_val)
            
    return results