一个近乎有序的数组,每个元素移动的距离一定不会超过k,进行排序

数组,每个元素移动的距离一定不会超过k,进行排序"/>

一个近乎有序的数组,每个元素移动的距离一定不会超过k,进行排序

/*** API提供的堆,优先级队列** 已知:*      一个近乎有序的数组,几乎有序是指,如果把数组排好序的话,每个元素移动的距离一定不会超过k*      并且k相对与数组长度来说是比较小的*/

public class ApiHeap {public static void main(String[] args) {//一个近乎有序的数组,使其元素达到该去的位置步数不超过kint[] arr = {1,4,5,6,3,5,8,10,7,9,11,15,13,18,15,17};heapsort(arr,5);System.out.println(Arrays.toString(arr));}public static void heapsort(int[] arr,int k){PriorityQueue<Integer> heap = new PriorityQueue<>();for (int i = 0; i < Math.min(arr.length, k); i++) {heap.add(arr[i]);}System.out.print("[");while (k < arr.length){System.out.print(heap.poll() + ", ");heap.add(arr[k]);k ++;}int lock = heap.size();//未进行弹出操作之前,已经加入了k个元素,所以会有剩余在堆中while (!heap.isEmpty()){if(lock != 1){System.out.print(heap.poll() + ", ");}else{System.out.print(heap.poll());}lock --;}System.out.println("]");}
}

 左神算法学习