Implement an Out-of-Order Sort Buffer with a Heap in Python

import heapq
from collections import deque


class OutOfOrderSorter:
    def __init__(self, buffer_size):
        self.buffer_size = buffer_size
        self.buffer = deque(maxlen=buffer_size)
        self.heap = []
        self.next_expected_index = 0
        self.result = []

    def push(self, item):
        heapq.heappush(self.heap, item)
        self._flush_ready()

    def _flush_ready(self):
        while self.heap and self.heap[0] == self.next_expected_index:
            item = heapq.heappop(self.heap)
            self.result.append(item)
            self.next_expected_index += 1

    def finish(self):
        while self.heap:
            item = heapq.heappop(self.heap)
            self.result.append(item)
        return self.result


if __name__ == "__main__":
    sorter = OutOfOrderSorter(buffer_size=3)
    # items arrive out of order: (index, value)
    stream = [(3, "c"), (1, "a"), (2, "b"), (0, "start"), (5, "e"), (4, "d")]
    for idx, val in stream:
        sorter.push(idx)
    print(f"Buffered indices: {sorter.buffer}")
    print(f"Heap: {sorter.heap}")
    print(f"Sorted output: {sorter.finish()}")