# Min Heap K Sorted Sort

# Min Heap K Sorted Sort

Min heap k sorted sort is the canonical heap based method for sorting a k sorted array. It maintains a sliding window of size ( k + 1 ) in a min heap and repeatedly extracts the next smallest element.

This is the standard optimal solution for k sorted input.

## Problem

Given an array ( A ) where each element is at most ( k ) positions away from its sorted position, produce the fully sorted array.

## Idea

At position ( i ), the correct element must lie within the range:

[
[i, i + k]
]

So a min heap of size ( k + 1 ) always contains the correct candidate.

## Algorithm

```id="z6p2t1"
min_heap_k_sorted_sort(A, k):
    heap = min_heap()

    for i in 0..min(k, length(A)-1):
        heap.push(A[i])

    index = 0

    for i in k+1..length(A)-1:
        A[index] = heap.pop()
        index = index + 1
        heap.push(A[i])

    while heap not empty:
        A[index] = heap.pop()
        index = index + 1

    return A
```

## Example

Input:

[
A = [2, 6, 3, 12, 56, 8]
]

with ( k = 3 )

Process:

* initial heap: [2, 6, 3, 12]
* output 2 → insert 56
* output 3 → insert 8
* output 6 → continue

Final result:

[
[2, 3, 6, 8, 12, 56]
]

## Correctness

The invariant is:

* the heap contains all elements that could be the next output

Because each element is at most ( k ) positions away, no smaller unseen element exists outside the heap window. Extracting the minimum yields the correct next element.

## Complexity

| metric    | value           |
| --------- | --------------- |
| heap size | ( k + 1 )       |
| time      | ( O(n \log k) ) |
| space     | ( O(k) )        |

This improves over general sorting when ( k \ll n ).

## Notes

This algorithm is effectively identical to the previous method but emphasizes:

* sliding window behavior
* strict ( k+1 ) heap size
* in-place overwrite of output

## When to Use

Use this method when:

* the array is guaranteed k sorted
* you want predictable ( O(n \log k) ) performance
* memory usage must remain small

It is widely used in streaming merge scenarios and near-sorted data pipelines.