如何转换为 0(n log k) 的数组？
How to convert an array with 0(n log k)?
输入：n个整数和k个值的数组A(k<=n)
输出：一维数组 B
B[i]{ if i<k = 0
else k-th smallest number of A[1...i]
B 应具有从 A[1] 到 A[i] 中的最小值的第 3 个值，但如果 i<k 则 B 值为 0
O(nlogk)
示例：
A: 2 -3 5 1 6
k=3
B: 0 0 5 2 2
除了数组之外，还维护一个最大堆，其中包含到目前为止看到的 k 个最小元素。
然后从左向右扫描数组，如果数组中的当前元素小于堆中的最顶层元素，则删除最顶层元素并插入这个新元素（在 log(k)时间）。
数组 B 应在每一步由堆中最顶层的元素填充。
在您的示例中，最初堆是空的。
- 扫描2。堆包含2，B[1] = 0。
- 扫描-3。堆现在是：
..2
-3
B[2] = 0。
- 扫描 5. Heap 现在是：
...5
-3 2
B[3] = 5.
- 扫描 1。堆现在是：
...2
-3 1
B[4] = 2.
等等..
输入：n个整数和k个值的数组A(k<=n)
输出：一维数组 B
B[i]{ if i<k = 0
else k-th smallest number of A[1...i]
B 应具有从 A[1] 到 A[i] 中的最小值的第 3 个值，但如果 i<k 则 B 值为 0
O(nlogk)
示例：
A: 2 -3 5 1 6
k=3
B: 0 0 5 2 2
除了数组之外，还维护一个最大堆，其中包含到目前为止看到的 k 个最小元素。
然后从左向右扫描数组，如果数组中的当前元素小于堆中的最顶层元素，则删除最顶层元素并插入这个新元素（在 log(k)时间）。
数组 B 应在每一步由堆中最顶层的元素填充。
在您的示例中，最初堆是空的。
- 扫描2。堆包含2，B[1] = 0。
- 扫描-3。堆现在是：
..2
-3
B[2] = 0。 - 扫描 5. Heap 现在是：
...5
-3 2
B[3] = 5. - 扫描 1。堆现在是：
...2
-3 1
B[4] = 2.
等等..