数据结构——堆（带图详解）

public class MyPriorityQueue {
    Integer[] array;
    int size;   // 有效元素的个数

    public MyPriorityQueue(){
        array = new Integer[11];
        size = 0;
    }

    public MyPriorityQueue(int initCapacity){
        if(initCapacity < 1){
            throw new IllegalArgumentException("初始容量小于1");
        }

        array = new Integer[initCapacity];
        size = 0;
    }

    public MyPriorityQueue(Integer[] arr){
        // 1. 将arr中的元素拷贝到数组中
        array = new Integer[arr.length];
        for(int i = 0; i < arr.length; ++i){
            array[i] = arr[i];
        }
        size = arr.length;

        // 2. 找当前完全二叉树中倒数第一个叶子节点
        //    注意：倒数第一个叶子节点刚好是最后一个节点的双亲
        //    最后一个节点的编号size-1  倒数第一个非叶子节点的下标为(size-1-1)/2
        int lastLeafParent = (size-2)/2;

        // 3. 从倒数第一个叶子节点位置开始，一直到根节点的位置，使用向下调整
        for(int root = lastLeafParent; root >= 0; root--){
            shiftDown(root);
        }
    }

    boolean offer(Integer e){
        if(e == null){
            throw new NullPointerException("插入时候元素为null");
        }

        ensureCapacity();

        array[size++] = e;

        // 注意：当新元素插入之后，可能会破坏对的性质---需要向上调整
        shiftUp(size-1);
        return true;
    }

    // 将堆顶的元素删除掉
    public Integer poll(){
        if(isEmpty()){
            return null;
        }

        Integer ret = array[0];

        // 1. 将堆顶元素与堆中最后一个元素交换
        swap(0, size-1);

        // 2. 将堆中有效元素个数减少一个
        size--;  // size -= 1;

        // 3. 将堆顶元素往下调整到合适位置
        shiftDown(0);
        return ret;
    }

    public int size(){
        return size;
    }

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

    public void clear(){
        size = 0;
    }

    // 功能：调整以parent为根的二叉树
    //    前提：必须要保证parent的左右子树已经满足堆的特性
    // 时间复杂度：O(logN)
    private void shiftDown(int parent){
        // 默认让child先标记左孩子---因为：parent可能有左没有右
        int child = parent*2 + 1;

        // while循环条件可以保证：parent的左孩子一定存在
        //       但是不能保证parent的右孩子是否存在
        while(child < size){
            // 1. 找到左右孩子中较小的孩子
            if(child+1 < size && array[child+1] < array[child]){
                child += 1;
            }

            // 2. 较小的孩子已经找到了
            //    检测双亲和孩子间是否满足堆的特性
            if(array[parent] > array[child]){
                swap(parent, child);

                // 大的双亲往下走了，可能会导致子树又不满足堆的特性
                // 因此需要继续往下调整
                parent = child;
                child = parent*2 + 1;
            }else{
                // 以parent为根的二叉树已经是堆了
                return;
            }
        }
    }

    private void shiftUp(int child){
        int parent = (child-1)/2;

        while(child != 0){
            if(array[child] < array[parent]){
                swap(child, parent);
                child = parent;
                parent = (child-1)/2;
            }else{
                return;
            }
        }
    }

    private void ensureCapacity(){
        if(array.length == size){
            int newCapacity = array.length*2;
            array = Arrays.copyOf(array, newCapacity);
        }
    }

    // 注意：left和right是数组的下标
    private void swap(int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

2、堆排序

• 升序：建大堆
• 降序：建小堆

public static void swap(int[] array, int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void shiftDown(int[] array, int size, int parent){
        int child = parent*2+1;

        while(child < size){
            // 找左右孩子中较大的孩子
            if(child+1 < size && array[child+1] > array[child]){
                child += 1;
            }

            // 双亲小于交大的孩子
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent*2+1;
            }else{
                return;
            }
        }
    }

    // 假设：升序
    public static void heapSort(int[] array){
        // 1. 建堆----升序：大堆    降序：小堆---向下调整
        for(int root = (array.length-2)/2; root >= 0; root--){
            shiftDown(array, array.length, root);
        }


        // 2. 利用堆删除的思想来排序---向下调整
        int end = array.length-1;   // end标记最后一个元素
        while(end != 0){
            swap(array,0,end);
            shiftDown(array, end,0);
            end--;
        }
    }

3、Top-k问题