k-messed-array排序可以在O（1）空间中使用堆进行吗

Question

在熟悉的问题中，数组中的每个元素最多有k个位置距离其正确位置，无论是向左还是向右，最小堆实现如下。

创建一个大小为k 1的min-heap。因此，min堆的根是已排序数组的最小元素。对于剩余的n-（k 1）元素，在每次迭代中，选择是在[i]和已在堆中的元素之间。因此，在堆中插入[i]，堆化并提取min。这将继续填充已排序数组的a[i-k]元素。

时间复杂度：O（k）O（n-k）。对数（k）

空间复杂度：O（k）

我的问题是：这可以用O（1）空间复杂度来实现吗？

我在这里找到了一种方法，但感觉不到。有人能详细说明一下吗？

你可以在适当的地方这样做。从远端开始，使用最大堆而不是最小堆。将最后一块2k个元素放置到位。将第一个提取的元素存储在变量中；后续元素位于2k的最后一个块（包含堆结构）之前的空白位置，类似于常规堆。当只剩下1个方块时，将其堆入到位。最后一个O（n）过程需要“旋转”最终块回到初始块。旋转不是微不足道的，但可以在O（n）和O（1）空间中完成。

Answer 1

基本思想是将堆存储在数组中，使用它对数组的其余元素进行排序，然后对堆部分本身进行排序。

这是一个使用min-heap的变体，可能更容易理解。

>

对数组的第一个k 1元素进行堆化。堆的最小元素将是整个数组的最小值。

k+1  | n-(k+1)
heap | unsorted

将堆的最小元素与未排序部分的第一个元素交换并重新堆化。

k+1  | 1      | n-(k+2)
heap | sorted | unsorted

重复步骤2，直到不再有未处理的元素。此时，堆包含数组中最大的元素，其余元素按排序顺序排列。

k+1  | n-(k+1)
heap | sorted

对数组的堆部分排序

k+1         | n-(k+1)
sorted heap | sorted

将排序后的堆移动到数组的另一端。数组现在已排序。

n-(k+1)| k+1
sorted | sorted heap