【数据结构】从王者荣耀血条到滴滴派单：堆结构在真实世界的权力游戏

大家应该都有玩过王者荣耀这类游戏吧，那么大家有没有想过王者荣耀中优先攻击血量最少的单位是怎么做到的呢？

一. 堆

1. 堆的概念

堆实际就是在完全二叉树的基础上进行了一些调整。假设我们有一个集合K={k0，k1，k2，......，kn-1}，我们将K中所有的元素按完全二叉树的顺序存储方式存储在一个一维数组中，此时我们分为大根堆和小根堆两种堆：

大根堆

当Ki >= K2i+1 且 Ki>= K2i+2（这里的 ki 指的是元素，i 指的是下标）那么此时的堆就是一个大根堆

小根堆

当Ki <= K2i+1 且 Ki<= K2i+2（这里的 ki 指的是元素，i 指的是下标）那么此时的堆就是一个小根堆

 总结：堆的性质

•  堆中某个节点的值总是不大于或不小于其父节点的值；
•  堆总是一棵完全二叉树。

2. 堆的创建

通过上述我们已经知道了堆是什么，那么我们现在来手动创建一个堆：

2.1 小根堆

小根堆实现原理：

代码实现：

​
public class MyHeap {
    //首先我们堆底层是一个数组实现的
    int []elem;
    //需要一个变量记录有效元素个数
    int usedsize;

    //构造方法
    public MyHeap(){
        //这里我们给数组初始空间设置为10
        elem=new int[10];
    }

    //初始化数组中的值
    public void create(int []array){
        for(int i=0;i<array.length;i++){
            elem[usedsize++]=array[i];
        }
    }

    //将数组调整为小根堆(向下调整)
    public void create_down(){
        for(int parent=(usedsize-1-1)/2;parent>=0;parent--){
            //向下调整
            siftdown(parent,usedsize);
        }
    }
    //向下调整
    private void siftdown(int parent,int usedsize){
        //找到我们的孩子节点
        int child=parent*2+1;
        while(child<usedsize){
            //判断左孩子和右孩子的值哪个小
            if(child+1<usedsize&&elem[child]>elem[child+1]){
                child++;
            }
            //判断较小值是否比父亲节点小
            if(elem[child]<elem[parent]){
                //交换
                swap(child,parent);
                //此时调节完继续向下调整
                parent=child;
                child=parent*2+1;
            }else{//当本次没有发生交换，说明此时不需要向下调整了，因为下面的都是大根堆
                break;
            }
        }
    }
    //交换
    public void swap(int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }

}

​

2.2 大根堆

大根堆实现原理：

大根堆的实现原理和小根堆是一样的，都是通过不断的向下调整保证堆的性质，不同的是先找到子节点中更大的值，并且子节点的值大于父亲节点的值时就进行交换，这里的判断条件是和小根堆是相反的：

代码实现：

public class MyHeap {
    //首先我们堆底层是一个数组实现的
    int []elem;
    //需要一个变量记录有效元素个数
    int usedsize;

    //构造方法
    public MyHeap(){
        //这里我们给数组初始空间设置为10
        elem=new int[10];
    }

    //初始化数组中的值
    public void create(int []array){
        for(int i=0;i<array.length;i++){
            elem[usedsize++]=array[i];
        }
    }

    //将数组调整为大根堆(向下调整)
    public void create_down(){
        for(int parent=(usedsize-1-1)/2;parent>=0;parent--){
            //向下调整
            siftdown(parent,usedsize);
        }
    }
    //向下调整
    private void siftdown(int parent,int usedsize){
        //找到我们的左孩子节点
        int child=parent*2+1;
        while(child<usedsize){
            //判断左孩子和右孩子的值哪个大
            if(child+1<usedsize&&elem[child]<elem[child+1]){
                child++;
            }
            //判断较大值是否比父亲节点大
            if(elem[child]>elem[parent]){
                //交换
                swap(child,parent);
                //此时调节完继续向下调整
                parent=child;
                child=parent*2+1;
            }else{//当本次没有发生交换，说明此时不需要向下调整了，因为下面的都是大根堆
                break;
            }
        }
    }
    //交换
    public void swap(int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }

}

 3. 堆的基本操作

此时我们的堆已经创建好了，现在我们来学习一下堆的两个重要操作（插入和删除）：

堆的插入

堆的插入其实就分成两个步骤：

• 将元素插入到堆的最后节点后面（如果空间不够就进行扩容）
• 将插入的元素向上调整，直到满足我们堆的性质（变成大根堆或者小根堆）

向上调整的过程：

插入的实现代码：（这里的代码实现的是大根堆的插入）

  //堆的插入
    public void offer(int val){
        //判断数组是否满了
        if(isFull()){
            resize();
        }
        elem[usedsize++]=val;
        //向上调整恢复成大根堆
        sift_up();
    }

    //向上调整
    private void sift_up(){
        int cur=usedsize-1;
        int parent=(cur-1)/2;
        while(parent>=0){
            if(elem[cur]>elem[parent])
            {
                swap(cur, parent);
                //交换完后重新寻找位置
                cur=parent;
                parent=(cur-1)/2;
            }else{
                return;
            }
        }
        //循环结束调整完毕
    }
    public boolean isFull(){
        return usedsize==elem.length;
    }

堆的删除

堆的删除：删除的是堆顶元素

1. 首先我们将堆顶元素和最后一个元素进行交换
2. 将堆中有效数据的个数减少有一个
3. 此时再从堆顶进行向下调整（让堆恢复成大根堆或者小根堆）

 调整过程：

代码实现：（这里的代码实现的是大根堆的删除）

  public int poll(){
        //判断队列为不为空
        if(isEmpty())
        {
            //抛出异常
            throw new PriQueueException("队列为空，删除错误！");
        }
        //交换最大值和最后一个结点的值
        int val=elem[0];
        swap(0,usedsize-1);
        usedsize--;
        //从0下标向下调整
        creat_down(0);
        return val;
    }

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

4.堆排序

堆排序是八大排序之一，其时间复杂度能够达到O(n*logN)

堆排序原理: 

• 根据大根堆的性质，根节点的值一定是最大的，所以我们每次将最大的值与结尾节点的值进行交换
• 交换完成后再次进行向下调整,将第arr.length-end大的数调整到根节点
• 需要排序的数据个数-1（数据下标：因为数组末尾就是最大值，不要再进行排序了）

排序过程：

代码实现：

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {3, 7, 2, 89, 1, 4, 78, 9, 0, 6, 5};
        creatHeap(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void creatHeap(int []arr){
        heap(arr);//创建大根堆
        int end=arr.length-1;
        while(end>=0){//开始排序
            swap(arr,0,end);//每一轮将最大值放到最后
            suifDown(arr,0,end);//将最大值放到最后之后,重新调整
            //需要排序的数的个数-1;
            end--;
        }
    }

    public static void heap(int []arr){
        //首先采用向下调整的方式创建一个大根堆
        int prare=(arr.length-1-1)/2;
        for(int i=prare;i>=0;i--){
            suifDown(arr,i,arr.length);
        }
    }
    public static void suifDown(int []arr,int parent,int len){
        int child=parent*2+1;//child表示当前parent位置下的左子树
        while(child<len){
            //开始调整
            if(child+1<len&&arr[child]<arr[child+1]){//表示右子树存在并且左子树的值小于右子树的值
                child++;
            }
           if(arr[child]>arr[parent]){
               swap(arr,child,parent);//将每棵子树的最大值放到根节点上
           }
            //向下调整
            parent=child;
            child=parent*2+1;
        }
    }
    public static void swap(int []arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
}

二. 优先级队列

优先级队列（Priority Queue）与普通队列都具有先进先出的特点，但是不同的是优先级队列中优先级最高的元素总是最先被取出，无论什么时候被插入，元素按照优先级队列顺序被处理，而不是按照插入顺序

 注意：

我们可以将堆看成是一个优先级队列，但是优先级队列不能看成是一个堆，这是因为堆是优先级队列的一种实现方式，优先级队列的实现方式有很多种，所以优先级队列不一定是堆

 在我们Java集合框架中提供了PriorityQueue这种类型的优先级队列，那么我们接下来看看PriorityQueue中的一些方法：

PriorityQueue的使用

PriorityQueue的构造方法

 PriorityQueue的方法摘要

 PriorityQueue使用的注意事项

• 使用时必须导入PriorityQueue所在的包：import java.util.PriorityQueue；
•  PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
• 不能插入null对象，否则会抛出NullPointerException 
• 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
• 插入和删除元素的时间复杂度为
• PriorityQueue底层使用了堆数据结构
• PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

 PriorityQueue默认情况下是小堆，那么有没有办法将其改成大堆呢？

此时需要我们自定义一个比较器，重写compare方法

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

class Compare_big implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Test {
    public static void main(String[] args) {
        int[] arr = {3, 7, 2, 89, 1, 4, 78, 9, 0, 6, 5};
        //创建比较器对象
        Compare_big compare_big=new Compare_big();
        PriorityQueue<Integer> queue= new PriorityQueue<>(compare_big);
        for(int i=0;i<arr.length;i++){
            queue.add(arr[i]);
        }
        for(int i=0;i<arr.length;i++){
            System.out.print(queue.poll()+" ");
        }
    }
}

结语

那么以上就是本篇的全部内容啦，感谢大家的观看~