# 1. 题目描述
给定一个几乎有序的数组，几乎有序是指如果把数组排好序，每个元素移动的距离不超过`K`，并且`K`相对于数组的长度是比较小的。请选择一个合适的算法来堆这个数组进行排序。
# 2. 题解
因为如果将数组排好序，每个元素移动的距离不超过`K`。比如排序好的数组`arr=[2, 5, 6, 8, 10, 15, 16, 19, 21]`，假定此时`K=3`那么这个几乎有序数组可以为：`[8, 2, 5, 6, 10, 19, 21, 16, 15]`。
因为每个元素移动的距离不超过`K`，换句话说也就是我们只从左到右遍历，保证对扫描到的元素`K+1`个元素进行排序，保证首个元素为最小值即可。所以可以建立一个大小为`K+1`的小根堆来解决这个问题。
~~~
public class HeapSortExtend {
public static void main(String[] args) {
int[] arr = new int[]{8, 2, 5, 6, 10, 19, 21, 16, 15};
new HeapSortExtend().sortByHeap(arr, 3);
for (int i : arr) {
System.out.print(i+"\t");
}
}
private void sortByHeap(int[] arr, int K){
// 定义小根堆
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
int heapSize = K + 1;
int i = 0;
for (; i < heapSize; i++) {
heap.add(arr[i]);
}
int j = 0;
for (; i < arr.length; j++) {
heap.add(arr[i++]);
arr[j] = heap.poll();
}
while(!heap.isEmpty()){
arr[j++] = heap.poll();
}
}
}
~~~
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-06 103310.png'/>
当然，这里也可以来仿写一下`PriorityQueue`：
~~~
static class MinHeap{
private int[] arr;
private int index = 0;
public MinHeap(){
this(512);
}
public MinHeap(int cap){
arr = new int[cap];
}
public void add(int val){
arr[index++] = val;
for (int i = 0; i < index; i++) {
heapInsert(i);
}
}
public boolean isEmpty(){
return index == 0;
}
public int poll(){
int val = arr[0];
int size = --index;
swap(arr, 0, size); // 和最后一个交换
// 保证继续是小根堆
heapify(size);
return val;
}
private void heapify(int size) {
int i = 0, left = 1;
while(left < size){
int minest = left + 1 < size && arr[left] > arr[left + 1] ? left + 1: left;
minest = arr[i] < arr[minest] ? i : minest;
if(minest == i) break;
swap(arr, i, minest);
i = minest;
left = i * 2 + 1;
}
}
private void heapInsert(int i) {
while(arr[i] < arr[(i - 1) / 2]){
swap(arr, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = arr[left] ^ temp;
arr[right] = arr[left] ^ temp;
}
}
~~~
替换`PriorityQueue`替换即可。
