排序K-排序阵列最小堆 [英] Sorting k-sorted arrays with a min heap

问题描述

一个很好的解决方案，以整理K-排序数组（每个元素超过k远离其目标位置），

A good solution to sorting k-sorted arrays(each element is at most k away from its target position) is,

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-排序？

I can't understand the relevance of the array being k-sorted to using the heap technique. Won't this work even when the array is not k-sorted?

推荐答案

原因当数组不是k排序这是不行的。

Of cause this will not work when the array is not k-sorted.

由于总是排序后的第一个元素是第K + 1个元素之间的最小元素，依此类推。

Because the first element after sorting always be the minimal element among the first k+1 elements, and so on.

有@leventov我们展示了一个例子。

@leventov have show us an example.

这篇关于排序K-排序阵列最小堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！