# 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`替換即可。
