堆排序java

1.堆结构就是用数组实现的完全二叉树结构
2.完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3.完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4.堆结构的heapInsert和heapify操作
5.堆结构的增大和减少
6.优先级队列结构，就是堆结构

先让整个数组都变成大根堆结构
把堆的最大值和堆末尾的值交换，然后减少堆的大小以后，再去调整堆，一直周而复始，时间复杂度O(N*logN)
堆的大小减小成0之后，排序完成

父节点与子节点的关系：左叶子节点：2*N+1，右叶子节点：2*N+2
子节点与父节点的关系：父节点 (N-1)/2

private void heapSort(int[] arr){
	if (null == arr || arr.length < 2){
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr,i);
    }
    int size = arr.length;
    swap(arr, 0, --size);
    while (size != 0){
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}
//从下往上，调成大根堆
private void heapInsert(int[] arr, int index){
	while(arr[index] > arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index-1)/2;
    }
}

//重新调整堆结构
private void heapify(int[] arr, int index, int size){
	int left = 2 * index + 1;
    while (left < size){
         int largest = (left+1 < size) && arr[left] arr[largest] ? index : largest;
         //如果最大值是父节点处，那么就停止循环，因为接下来的结构都是之前调整好的
         if (largest == index){
             break;
         }
         swap(arr,largest,index);
         index = largest;
         left = 2 * index + 1;
     }
}

private void swap(int[] arr, int i, int j){
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

【题目】
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，
每个元素移动的距离可以不超过K，并且k相对于数组来说比较小，
请选择一个合适的算法进行排序
【思路】优先级队列是用堆实现的，可以直接利用优先级队列,把优先级队列直接当做堆排序就好

private void sortedArrDistanceLessK(int[] arr, int k){
	PriorityQueue heap = new PriorityQueue<>();
    int index = 0;
    for (; index < Math.min(k, arr.length); index++) {
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < arr.length; i++, index++) {
        arr[i] = heap.poll();
        heap.add(arr[index]);
    }

    while (!heap.isEmpty()){
        arr[i++] = heap.poll();
    }
}