使用最小堆排序k个已排序数组

Question

一个好的解决方案是对于k-sorted数组（每个元素距其目标位置最多为k），可以采用以下方法进行排序：

1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time. 

2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

overall complexity will be O(k) + O((n-k)*logK)

我不理解数组被k排序与使用堆技术之间的关联。即使数组没有经过k排序，这种方法仍然有效吗？

- Aks

---

[1, 2, 3, 0]，k=2 - leventov

为了完整起见，以上算法与@leventov的示例结果为[1, 2, 0, 3]。 - Vincent van der Weele

Answer 1

当数组未经过k排序时，这种方法是无效的。因为在排序后，第一个元素总是前k+1个元素中最小的，以此类推。@leventov已经给我们提供了一个例子。

- Liu Ameng

Answer 2

A: 从一个数组中找到k个最小的数（不一定排序）：
你认为的方法可以完美地在O(k) + O((n-k)*logK)时间内运行。

B: 对数组进行排序：
在每一步中，你从大小为k的堆中找到最小的数字，但如果数组中的最小数字位于索引k + 2处怎么办？在你的算法中，它不会在第一步中被放置，直到你将其插入为止，你已经输出了两个数字，并认为它们<原始最小值。

所以，你肯定希望它们在排序后的位置上不超过k。

- Aseem Goyal