数据结构之优先级队列（堆）

一、二叉树的顺序存储使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。如图所示：下标的一些关系：已知双亲(parent)的下标，则：左孩子(left)下标 = 2 * parent + 1;右孩子(right)下标 = 2 * parent + 2;已知孩子（不区分左右）(child)下标，

爱吃小料的毛孩子

5056人浏览 · 2022-03-29 12:07:50

爱吃小料的毛孩子 · 2022-03-29 12:07:50 发布

一、二叉树的顺序存储

使用数组保存二叉树结构，方式即将二叉树用 层序遍历 方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。如图所示：

下标的一些关系：

已知双亲 (parent) 的下标，则：

左孩子(left)下标 = 2 * parent + 1;

右孩子(right) 下标 = 2 * parent + 2;

已知孩子（不区分左右） (child) 下标，则：

双亲(parent) 下标 = (child - 1) / 2。

二、堆

1.概念

（1）堆逻辑上是一棵完全二叉树（2）堆物理上是保存在数组中（3）满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆（4）堆的基本作用是，快速找集合中的最值

2.操作--向下调整、建堆

int [] array = { 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 };调整为大根堆

public class TestHeap {
    public int[] elem;
    public  int usedSize;

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

    public void shiftDown(int parent, int len){//parent:每颗树的根节点 len:每颗树调整的结束位置
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;//elem[child] < elem[parent]已经是大堆，所以跳出循环
            }
        }
    }

    public void createHeap(int[] array){
        for(int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for(int parent = ((this.usedSize-1)-1)/2; parent >= 0; parent--){
            shiftDown(parent,this.usedSize);
        }
    }
}

时间复杂度：O(n)

3.堆的应用--优先级队列

（1）概念

在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)，优先级队列的实现方式有很多，但最常见的是使用堆来构建

（2）一些方法

PriorityQueue默认是一个小根堆

（3）自定义入队列

①首先按尾插方式放入数组
②比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
③否则，交换其和双亲位置的值，重新进行 2、3 步骤
④直到根结点
如图所示

代码实现：

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public  int usedSize;

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

    public void shiftDown(int parent, int len){//parent:每颗树的根节点 len:每颗树调整的结束位置
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;//elem[child] < elem[parent]已经是大堆，所以跳出循环
            }
        }
    }

    public void createHeap(int[] array){
        for(int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for(int parent = ((this.usedSize-1)-1)/2; parent >= 0; parent--){
            shiftDown(parent,this.usedSize);
        }
    }
    private void shiftUp(int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }
    public void offer(int val){
        if(isFull()){
            //扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        elem[usedSize++] = val;
        shiftUp(usedSize - 1);
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }
}

（4）自定义出队列

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

public int poll(){
    if(isEmpty()){
        throw new RuntimeException("优先级队列为空！");
    }
    int tmp = elem[0];
    elem[0] = elem[usedSize - 1];
    elem[usedSize - 1] = tmp;
    usedSize--;
    shiftDown(0,usedSize);
    return tmp;
}
public boolean isEmpty(){
    return usedSize == 0;
}

（5）自定义返回队首元素

public int peek(){
    if(isEmpty()){
         throw new RuntimeException("优先级队列为空！");
    }
    return elem[0];
}

（6）topK问题

思路：（3种方法）

①对整体进行排序，输出前10个最大的元素

②建成大根堆，然后弹出前3个最大的元素即可，时间复杂度为O(n*logn)

③先把前K个元素创建为小根堆，因为堆顶的元素一定是当前K个元素当中最小的一个元素，如果有元素X比堆顶大，那么X这个元素可能就是topK的其中一个。（如果堆顶元素小，那么就出堆顶元素，然后入当前比堆顶大的元素，再次调整为小根堆）（堆的大小只有K这么大）时间复杂度为O(n*logn)

总结一下：

①如果求前K个最大（小）的元素，要建一个小（大）根堆

②第K大（小）的元素，建一个小（大）堆，堆顶元素就是第K大（小）的元素

思路③的代码实现：

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TopK {
    public static int[] topK(int[] array, int k){
        //创建一个大小为k的大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //遍历数组中的元素，前k个元素放在队列当中
        for(int i = 0; i < array.length; i++){
            if(maxHeap.size() < k){
                maxHeap.offer(array[i]);
            }else{
                //从第k+1个元素开始，每个元素和堆顶元素进行比较
                int top = maxHeap.peek();
                if(top > array[i]){
                    //先弹出
                    maxHeap.poll();
                    //后存入
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[] tmp = new int[k];
        for(int i = 0; i < k; i++){
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array = {18,21,8,10,34,12};
        int[] tmp = topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }
}

编译并运行该代码，输出如下：

[12, 10, 8]

4.堆排序

对一组数组进行从小到大的排序，我们要借助大根堆，然后将0下标和最后一个未排序的元素进行交换即可

如图所示：排序之前：27 15 19 18 28 34 65 49 25 37

public class TestHeap {
    public int[] elem;
    public  int usedSize;

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

    public void shiftDown(int parent, int len){//parent:每颗树的根节点 len:每颗树调整的结束位置
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;//elem[child] < elem[parent]已经是大堆，所以跳出循环
            }
        }
    }

    public void createHeap(int[] array){
        for(int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for(int parent = ((this.usedSize-1)-1)/2; parent >= 0; parent--){
            shiftDown(parent,this.usedSize);
        }
    }
    public void heapSort(){
        int end = this.usedSize - 1;
        while(end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }
}