堆，向下调整算法，向上调整算法，数组建堆，堆排序，Topk问题

堆

• 1.堆的基本概念， *** 作及实现
• • 1.1概念
  • 1.2 *** 作---向下调整
• 2.堆的应用---优先级队列
• • 2.1 *** 作---入队列
  • 2.2 *** 作---出队列
• 3.堆排序
• 4.Topk问题

1.堆的基本概念， *** 作及实现 1.1概念

1.概念：

1. 堆逻辑上是一颗完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意节点的值都大于其子树中节点的值叫做大堆，或者大根堆，特点arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
4. 满足任意节点的值都小于其子树中节点的值叫做小堆，或者小根堆，特点arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]
5. 堆的基本作用是，快速找到集合中的最值

2.下标关系
已知双亲(parent)下标则：
左孩子(left)下标 = 2*parent+1;
右孩子(right)下标 = 2*parent+2;
已知孩子(不区分左右)（child）下标则：
双亲(parent)下标 = (child -1) / 2;

示例：
如下数组

其展开图如下

1.2 *** 作—向下调整

前提：左右子树必须已经是一个堆才可以调整

说明：

1. array代表存储堆的数组
2. usedSize 代表数组数据的个数
3. parent 代表要调整位置的下标
4. left 代表 parent 左子树下标
5. right 代表 parent右子树下标
6. child代表 parent 最大孩子的下标

过程：(以大堆为例)
1.parent 如果已经是叶子结点，则调整过程结束

• 1.判断parent位置有没有孩子
• 2.因为堆是完全二叉树，没有左子树就一定没有右子树，所以判断是否有左子树
• 3因为堆的数据结构是数组，所以判断是否有左子树即判断左子树下标是否越界，即left>=size越界

2.确定 left 或 right，谁是 parent 的最大子树 child

• 1如果右子树不存在，则child=left
• 2否则，比较 array[left]和 array[right] 值的大小，选择大的为child

3.比较array[parent]的值和array[child]的值，
如果array[parent] > array[child],则满足堆的性质，调整结束
4.否则，交换array[parent] 和array[child]的值
5.然后因为child位置的堆的性质可能被破坏，所以把child视作parent，向下重复以上过程

以示例中的数组为例：调整前

向下调整完以后：

代码示例：

    public TestHeap() {
        this.elem = new int[10];//10个0
    }

    //将一个堆改为大堆
    public void shiftDown(int parent) {//向下调整
        int child = 2*parent+1;
        //进入这个循环 说明最起码你有左孩子
        while (child < this.usedSize) {
            //有右子树，并且右子树大于左子树
            if(child+1 < this.usedSize && this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //child所保存的下标，就是左右孩子的最大值
            if(this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];//交换
                this.elem[parent] = tmp;
                parent = child;//往下延伸，确保交换后依然满足大堆结构
                child = 2*parent+1;
            }else {
                break;//如果孩子节点比父亲节点小 直接结束了
            }
        }
    }

    //1 4 18 7 .....
    public void createBigHeap(int[] array) {
        //把需要的数据 存放到elem当中
        // 一会儿建堆的时候 直接 *** 作 elem数组就可以了
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }

        for (int i = (this.usedSize-1-1)/2; i >= 0 ; i--) {
            //从最后一棵树的树根开始
            shiftDown(i);
        }
    }//若是将一个堆改为小堆只需将shiftDown中的大于号和小于号修改一下即可

2.堆的应用—优先级队列

优先队列（大堆）

每次出队列的元素都是优先级最高的元素
优先级队列的实现方式有很多，但最常见的是使用堆来构建。

入队列的时候，就把元素插入到数组末尾，然后向上调整。

进行出队列的时候，就把堆顶的元素删除，并且进行向下调整

2.1 *** 作—入队列

过程（以大堆为例）：

1. 首先按尾插的方式放入数组
2. 比较其和其双亲的值的大小，若双亲的值大，则满足堆的性质，插入结束
3. 否则，交换其和双亲位置的值，重新进行2,3步骤
4. 直到根节点

如下图所示：

代码示例：

    public  boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    public void push(int val) {
        if(isFull()) {//判断是否已经满了，扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;//
        //向上调整
        shiftUp(this.usedSize-1);
    }
    public void shiftUp(int child) {//向上调整
        int parent = (child-1)/2;
        while (parent >= 0) {//调整终止条件，也可以是child==0
            if(this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

2.2 *** 作—出队列

为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整的方式重新调整成堆。

步骤：

1. 0下标元素和数组最后一个元素进行交换
2. usedSize–
3. 向下调整0下标元素即可

如图：

代码实现：

    //出队列
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空！");
        }
        //交换第一个元素和最后一个元素
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
        shiftDown(0);//对0下标进行向下调整
        return tmp;
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

3.堆排序

类似于选择排序
堆排序的基本思想是：

1. 将待排序序列构造成一个堆(升序排序用大根堆，若降序排序采用小根堆)，
2. 此时，整个序列的最大值就是堆顶的根节点。
   

3. 将堆顶元素与末尾元素进行交换，此时末尾就为最大值。
   

4. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
   

   如此反复执行，便能得到一个有序序列了

如图所示：
步骤一：构建初始堆，将一个无序序列构造成一个大根堆(升序采用大根堆，将需采用小根堆)
1.假定给定的无序序列结构如下
arr [4,6,8,5,9]

2.此时我们从最后一个非叶子节点开始(叶子结点不用调整，第一个非叶子节点 arr.length/2-1=5/2-1=1,也就是下面的6结点)，从左至右，从上至下进行调整。

3.找到第二个非叶子节点4，由于[4,9,8]中9元素最大，4和9交换

4.这时，交换导致了子根[4,5,6]结构混乱继续调整，[4,5,6]中6最大，交换4和6

此时，我们就将一个无序序列构造成了一个大根堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换重建，交换。

1.将堆顶元素9和末尾元素4进行交换

2.重新调整结构，使其继续满足堆定义

3.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

4.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

代码示例：

    //堆排序
    public static void heapSort(int[] array) {
        createBigHeap(array);//建一个大根堆
        int end = array.length-1;
        while (end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }

    //建一个大根堆
    public static void createBigHeap(int[] array) {
        //
        for (int i = (array.length-1-1)/2; i >= 0 ; i--) {
            shiftDown(array,i,array.length);
        }
    }
    
    public static void shiftDown(int[] array,int parent,int len) {
        int child = 2*parent+1;
        while (child < len) {
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            //child下标 表示的就是左右孩子最大值的下标
            if(array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            }else {
                break;
            }
        }
    }

堆排序参考资料

4.Topk问题

Top K问题，是指在N个数的无序序列中找出前K个最大的数

排序是最容易想到的方法，将n个数排序之后，取出最大的k个，即为所得。

但明明只需要TopK，却将全局都排序了，这也是这个方法复杂度非常高的原因

思路：只找到TopK，不排序TopK

步骤：

1. 先用前k个元素生成一个小堆，这个小堆用于存储，当前最大的k个元素
2. 接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素
3. 直到，扫描完所有n-k个元素，最终堆中的k个元素，就是求的TopK

代码示例：

    public static int[] topK(int[] array,int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //Java中的优先级队列是小堆
        for (int i = 0; i < array.length; i++) {
            if(minHeap.size() < k) {//将前K个元素建成小堆
                minHeap.offer(array[i]);
            }else {
                int top = minHeap.peek();//获取堆顶元素
                if(top < array[i]) {
                    minHeap.poll();//出队
                    //入队，Java中会自动完成排序，小堆
                    minHeap.offer(array[i]);
                }
            }
        }
        //minHeap存储的就是前K个最大的元素
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

时间复杂度：O(n*lg(k))

n个元素扫一遍，假设运气非常差，每次都入堆调整，调整时间复杂度为堆的高度，即lg(k)，故整体时间复杂度是n*lg(k)。