K-Messed Array Sort
Given an array of integers
arr
where each element is at mostk
places away from its sorted position
Solution
from Queue import PriorityQueue
def sort_k_messed_array(arr, k):
kheap = PriorityQueue()
result = []
for num in arr:
kheap.put(num, 'num')
if kheap.qsize() == (k + 1):
item = kheap.get()
result.append(item)
while not kheap.empty():
result.append(kheap.get())
return result
arr = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9]
print(sort_k_messed_array(arr, 2))
Result
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]