Practice › Heap & Priority Queue
Sort a K-Sorted Array
Medium · Heap & Priority Queue · Asked at Amazon, Microsoft, Flipkart
Every element is at most k positions away from where it would be in the sorted array. Sort the array in O(n log k).
Input
First line: n k. Second line: n integers.
Output
The sorted array.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ k < n
The smallest element must be among the first k + 1. Keep a min-heap of k + 1 elements; pop the minimum, push the next element.
Example 1
Input
7 3 6 5 3 2 8 10 9
Output
2 3 5 6 8 9 10
Example 2
Input
5 0 1 2 3 4 5
Output
1 2 3 4 5
Hints
- The smallest element of the whole array must be among the first k + 1 elements.
- Slide a min-heap of size k + 1 along the array: pop the minimum into the output, push the next element.
Approach
Fill a min-heap with the first k + 1 elements. Then for each remaining element: pop the minimum (it is the next element of the sorted order, since nothing further away can be smaller) and push the new element. Finally pop everything left. Each heap operation is O(log k).
Complexity: O(n log k) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
priority_queue<long long, vector<long long>, greater<long long>> pq;
vector<long long> out;
for (int i = 0; i < n; i++) {
pq.push(a[i]);
if ((int)pq.size() > k) out.push_back(pq.top()), pq.pop();
}
while (!pq.empty()) out.push_back(pq.top()), pq.pop();
for (int i = 0; i < n; i++) cout << out[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
heap, out = [], []
for x in a:
heapq.heappush(heap, x)
if len(heap) > k:
out.append(heapq.heappop(heap))
while heap:
out.append(heapq.heappop(heap))
print(*out)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
PriorityQueue<Long> pq = new PriorityQueue<>();
StringBuilder sb = new StringBuilder();
int printed = 0;
for (int i = 0; i < n; i++) {
pq.add(sc.nextLong());
if (pq.size() > k) sb.append(printed++ > 0 ? " " : "").append(pq.poll());
}
while (!pq.isEmpty()) sb.append(printed++ > 0 ? " " : "").append(pq.poll());
System.out.println(sb);
}
}