数组实现堆

• 利用位运算加快节点查找速度。根节点从1开始，0位置舍弃。
• 从0位置开始，左孩子 =i2+1,右孩子=i2+2。

大根堆。

1. 构建大根堆流程。

• 在数组中依次加入元素，当前元素和和父亲节点比较
  1.如果当前节点小于父亲节点则停止。
  2.如果当前节点大于父亲节点，则和父亲节点交换，当前节点变为父亲节点。
  3.重复上述步骤直到小于父亲节点，或者当前节点就是父亲节点。

2. 弹出堆顶元素。

• 弹出堆顶元素，调整堆，使其重新变为大根堆。流程如下
  1.弹出堆顶元素，用数组中最后一个元素填补堆顶元素。
  2.重堆顶元素开始向下调整元素结构，如果堆顶元素大于等于其左右孩子的最大值则停止调整，若小于其左右孩子的最大值，则继续进行下面操作。
  3.把当前元素和左右孩子的最大值交换。
  4.重复2步骤直到不能交换为止。
• 代码如下

public class Heap {

    // 数组代表堆结构
    private int[] heap;
    // 当前堆大小
    private int heapSize;
    // 堆得容量
    private int limit;
    public Heap(int limit){
        this.heap = new int[limit];
        this.limit = limit;
        this.heapSize = 0;
    }
    // 构建堆
    public void push(int value) throws Exception {
        heapInsert(value);
    }

    // 弹出堆顶元素
    public  int pop() throws Exception {
        if(heapSize == 0){
            throw new Exception("堆为空！");
        }
        int res = heap[0];
        // 交换堆顶元素和最后一个元素,堆大小减1
        swap(heap,0,--heapSize);
       heapIfy(heap,0);
        return res;
    }

    public  boolean isFull(){
        return this.heapSize == this.limit;
    }

    public boolean isEmpty(){
        return heapSize == 0;
    }

    // heapify
    private void heapIfy(int[] heap,int index){
        // 重新调整堆，使其变为大根堆
        // 计算其左孩子的下标
        int left = index * 2 + 1;
        // 有最孩子则继续调整
        while (left < heapSize){
            // 计算最有孩子中值最大的下标
            int largest = (left + 1 < heapSize) && heap[left] < heap[left + 1] ? left + 1 :left;
            // 比较父节点和左右孩子最大值谁大
            largest = heap[index] >= heap[largest] ? index : largest;
            if(largest == index){
                // 如果此时最大小标等于父节点下标，说明父节点值大，不用调整
                break;
            }
            // 交换
            swap(heap,largest,index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    // heapInsert,给我一个元素，加入堆中，把堆调整为大根堆
    private void heapInsert(int value) throws Exception {
        if(heapSize == limit){
            throw new Exception("堆已满");
        }
        // 首先把元素加入数组中
        this.heap[heapSize++] = value;
        // 调整堆结构
        // 父元素下标
        int index = ((heapSize - 1) - 1) / 2;
        // 只要当前元素大于父元素就一直调整
        int cur = heapSize -1;
        while (heap[cur] > heap[index]){
            swap(heap,index,cur);
            cur = index;
            index = (index-1) / 2;

        }
    }

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

堆排序（时间复杂度O(nlogn)，空间复杂度O(1)）

• 利用大根堆，每次都把堆顶元素放在未排好序区域的最后一个。

public class HeapSort {
    public void heapSort(int[] arr) throws Exception {
        if(arr == null || arr.length < 2){
            return;
        }
//        for (int i = 0; i < arr.length; i++) {
//            // 相当于一个一个加进去，调整为大根堆
//            // O(nlogn) n 个数每次调整代价都是log(n)
//            heapInsert(arr,i);
//        }

        for (int i = arr.length - 1; i >= 0 ; i--) {
            // O(n)
            heapIfy(arr,i,arr.length);
        }
        int size = arr.length - 1;
        while (size >= 0){
            swap(arr,0,size);
            heapIfy(arr,0,size--);
        }


    }

    private void heapInsert(int[] arr,int index) throws Exception {
        while (arr[index] > arr[(index - 1) / 2]){
            swap(arr,index,(index - 1) / 2);
            index = (index-1) / 2;

        }
    }

    private void heapIfy(int[] heap,int index,int heapSize){
        // 重新调整堆，使其变为大根堆
        // 计算其左孩子的下标
        int left = index * 2 + 1;
        // 有最孩子则继续调整
        while (left < heapSize){
            // 计算最有孩子中值最大的下标
            int largest = (left + 1 < heapSize) && heap[left] < heap[left + 1] ? left + 1 :left;
            // 比较父节点和左右孩子最大值谁大
            largest = heap[index] >= heap[largest] ? index : largest;
            if(largest == index){
                // 如果此时最大小标等于父节点下标，说明父节点值大，不用调整
                break;
            }
            // 交换
            swap(heap,largest,index);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

}

相关题目

• 已知一个几乎有序的数组，几乎有序是指，如果把数组排好序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说相对小，选择一个合适的排序策略对数组进行排序。

public class K_HeapSort {

    public static void sort(int[] arr,int k){
        if(arr == null || arr.length < 2 || k <= 0){
            return;
        }

        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 先把前 k个数加入小根堆
        for (int i = 0; i < k; i++) {
            heap.add(arr[i]);
        }
        int index = 0;
        for (int i = k + 1; i < arr.length; i++) {
            // 堆顶弹出最小值，放入数组相应下标
            arr[index++] = heap.poll();
            heap.add(arr[i]);
        }

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

什么时候用系统堆，什么时候自己改写堆

• 如果元素入堆以后只有加入和弹出操作，那么用系统堆就够了。
• 如果元素入堆以后，会改变元素的值（引用类型），那么需要改写堆，支持重新调整堆结构。
  1.利用一张hash表记录入堆元素的下标，每次元素值改变是，通过hash表找到元素，进行堆结构调整。

比较器 Comparator 接口