AlgoDesign

Sort almost sorted array

1from heapq import *
2class Solution:
3    def sortAlmostSortedArray(self, arr, k):
4        res, minHeap = [], []
5
6        for i in range(k): heappush(minHeap, arr[i])
7        for i in range(k, len(arr)):
8            num = heappushpop(arr[i])
9            res.append(num)
10        while minHeap: res.append(heappop(minHeap))
11
12        return res