珠海企业网站制作费用/制作一个网站的全过程

已知一个几乎有序的数组。几乎有序是指，如果把数组拍好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。

用堆来解决这个问题，首先贴上堆结构

package dataStruct;public class Heap {private int[] arr;private int heapSize;public Heap(int n) {this.arr = new int[n];this.heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == arr.length;}private void swap(int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}public void add(int val) {if (isFull()) {throw new RuntimeException("heap is Full");}arr[heapSize] = val;heapIndex(heapSize++);}public Integer remove() {Integer ret = arr[0];swap(0, --heapSize);heapify(0);return ret;}/*** 向下看，看看能不能向下走* @param index*/private void heapify(int index) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[largest] > arr[index] ? largest : index;if (index == largest) {break;}swap(index, largest);index = largest;left = index * 2 + 1;}}/*** 向上看，能不能往上走* @param val*/private void heapIndex(int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(index, (index - 1) / 2);index = (index - 1) / 2;}}public void heapSort(int[] arr) {for(int i = 0;i<arr.length;i++) {heapIndex(i);}int heapSize = arr.length;while(heapSize>0){swap(--heapSize,0);heapify(0);}}}

已知每个元素移动的距离一定不超过k，那么我建立一个长度为k+1的小根堆结构，如果将0-k的数放入堆中，那么排完序的数组0位置的数，就一定在我的堆中，因为移动的距离不超过k，那么我将堆中的堆顶元素取出，这个元素一定是排在排序完成后的数组的第一位，并且将数组的下位压入堆中，再次进行排序，覆盖掉堆顶，重新排序为堆结构，以此类推。代码如下：

	public void sortedArrDisrtanceLess(int[] arr, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>();int index = 0;for (; index <= Math.min(k, arr.length-1); index++) {heap.add(index);}for (int i = 0; i < arr.length; i++) {arr[i] = heap.poll();if (index < arr.length) {heap.add(index++);}}}