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