Java -数据结构，【优先级队列 / 堆】

偏执的太偏执、 2024-03-26 17:28 111阅读 0赞

## 一、二叉树的顺序存储 ##

在前面我们已经讲了二叉树的链式存储，就是一棵树的左孩子和右孩子  
而现在讲的是：顺序存储一棵二叉树。

### 1.1、存储方式 ###

> 使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。  
> 这种方式的主要用法就是堆的表示  
> ![在这里插入图片描述][492b11e94c044a26a178f8adb21810ff.png]

**下标关系**

**已知双亲(parent)的下标，则：**  
左孩子(left)下标 = 2 \* parent + 1;  
右孩子(right)下标 = 2 \* parent + 2;

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

**也就是前面我们将的性质5：**  
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

> （1）若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点  
> （2）若2i+1<n，左孩子序号：2i+1，否则无左孩子  
> （3）若2i+2<n，右孩子序号：2i+2，否则无右孩子  
> ![在这里插入图片描述][5b500fd24f014af2a1ab5f369e58ff1e.png]

## 二、堆 ##

### 2.1、概念 ###

> 1.  堆逻辑上是一棵完全二叉树
> 2.  堆物理上是保存在数组中
> 3.  满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
> 4.  反之，则是小堆，或者小根堆，或者最小堆
> 5.  堆的基本作用是，快速找集合中的**最值** ：无论是 大根堆还是小根堆， 它们的 最值【最大值 和 最小值】都处于 二叉树的 根结点处。要想获得 最值，直接 peek 方法，就能获得 树 的 根结点值 / 最值。![在这里插入图片描述][7447f2dae313445a9974191ec41454cb.png]  
>     ![在这里插入图片描述][9b212bcde589435d9c1fc3ea7ae5274a.png]

### 2.2、操作-向下调整 ###

前提：左右子树必须已经是一个 堆 / 逻辑上是一棵完全二叉树。  
**将一组 记录完全二叉树数据 的 数组 转换成 大根堆。**  
![在这里插入图片描述][b2ae1cbb3ed14bab93087912710b26b2.png]

**向下调整出现的问题：**

> ![这里是引用][06dc943c35854e0682538fb5126f4cbd.png]  
> **得出结论:其实每棵树的调整结束位置都是一样的︰不能超过数组长度。**

**如何构造一个 向下调整的函数 - 重点**  
![在这里插入图片描述][caafefdeab704c7881f3f5e97cc5c0a6.png]

public class TestHeap {
        
        public int[] elem;//底层是一个数组
        public int usedSize;
    
        //
        public TestHeap(){
        
            this.elem = new int[10];
        }
    
        /**
         * 创建堆
         * @param array 堆里面存放的元素
         */
        public void creatHeap(int[] array){
        
            //将array数组的元素存入elme 数组
            for (int i = 0; i < array.length; i++) {
        
                elem[i] = array[i] ;
                usedSize++;
            }
            for (int praent = (usedSize-1-1)/2; praent >= 0; praent--) {
        
                shiftDown(praent,usedSize);
            }
        }
    
        /**
         * 向下调整
         * @param praent 每棵子树的父亲节点
         * @param len 调整的结束位置，不能大于数组的长度
         */
        public void shiftDown(int praent, int len){
        
            int child = 2+praent +1;
            while (child < len){
        
                if(child + 1 > len && this.elem[child] < this.elem[child+1]){
        
                    child++;
                }
    
                if(elem[child] > elem[praent]){
        
                    int tmp = elem[child];
                    elem[child] = elem[praent];
                    elem[praent] = tmp;
    
                }else {
        
                    break;
                }
            }
        }
    }

**测试一下：**  
![在这里插入图片描述][d743502b629d4e95a67d768961691f37.png]

**模拟实现 堆 的 时间复杂度**  
![在这里插入图片描述][56d50e76407642379076b212783e1f50.png]  
上图转载于：[堆 / 优先队列][Link 1]

粗略估算，可以认为是在循环中执行向下调整，为 O(n \* log(n))  
（了解）实际上是 O(n)  
[堆排序中建堆过程时间复杂度O(n)怎么来的？][O_n]

### 2.3、操作-建堆 ###

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

**图示（以大堆为例）：**

// 建堆前
    int[] array = {
         1,5,3,8,7,6 };
    // 建堆后
    int[] array = {
         8,7,6,5,1,3 };

> ![这里是引用][6360b11a729e4b6e95e80b95d15ce964.png]

## 三、堆的应用-优先级队列 ##

### 3.1、概念 ###

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

**优先级队列的实现方式有很多，但最常见的是使用堆来构建**

### 3.2、堆的基本操作 ###

我们知道堆分为大根堆和小根堆，那Java中自带的默认是大根堆还是小根堆？？？  
**Java集合中默认是小根堆**

我们测试一下：

public static void main(String[] args) {
        
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(12);
            priorityQueue.offer(3);
            priorityQueue.offer(18);
    
            System.out.println(priorityQueue.poll());
            System.out.println(priorityQueue.poll());
    
        }

![在这里插入图片描述][b7350dee53164d6cb18a012e9be1a898.png]

**优先级队列 - 模拟实现入队 – offer（）**  
![在这里插入图片描述][1154919636394c89ae8b52304897d5e9.png]

/**
         *  插入元素
         * @param val
         */
        public void offer(int val){
        
            if(isFull()){
        
                //扩容
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            //没有满就将val放在数组的最后一个元素
            elem[usedSize] = val;
            usedSize++;
    
            //然后就调整堆，使其成为一个大根堆
            shiftUp(usedSize-1,val);
        }
    
    
        /**
         *
         * @param child 孩子节点的坐标
         * @param val 要插入的值
         */
        public void shiftUp(int child, int val){
        
            int praent = (child - 1) / 2;
    
            while(praent > 0){
        
                if(elem[child] > elem[praent]){
        
                    int tmp = elem[child];
                    elem[child] = elem[praent];
                    elem[praent] = tmp;
    
                    //然后再改变child 和 praent 的指向
                    child = praent;
                    praent = (child - 1) / 2;
                }else {
        
                    break;
                }
            }
        }
    
        public boolean isFull(){
        
            return this.elem.length == usedSize;
        }

![在这里插入图片描述][e17a197224924452b87f59d59ca0dc4c.png]

**优先级队列 - 模拟实现出队 – poll（）**  
![在这里插入图片描述][cfc68770b67a4606a2dae315a034d19a.png]

public int poll(){
        
            if(isFull()){
        
                throw new RuntimeException("队列为null！");
            }
            //先将0下标和数组的最后一个元素交换
            int tmp = elem[0];
            elem[0] = elem[usedSize-1];
            elem[usedSize-1] = tmp;
            usedSize--;
    
            //然后向下调整0下标这棵树
            shiftDown(0,usedSize);
            return tmp;
        }
        //判断是否为null
        public boolean isEmpty(){
        
            if (usedSize == 0){
        
                return true;
            }
            return false;
        }

**总程序**

public class Heap {
        
        public int[] elements;// 底层数组
        public int usedSize;// 有效元素个数
        // 构造方法
        public Heap(){
        
            // 数组初始化容量
            this.elements = new int[10];
        }
         // 创建堆，获取 输入数组 的 数据
        public void creationHeap(int[] array){
        
            this.usedSize += array.length;
            if(isFull()){
        
                this.elements = Arrays.copyOf(this.elements,this.elements.length*2);
            }
            this.elements = Arrays.copyOf(array,array.length);
    
            for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){
        
                // 向下调整
                shiftDown(parent,this.usedSize);
            }
        }
        // 向下调整
        public void shiftDown(int parent,int len){
        
            int child = parent * 2 + 1;// 左孩子
            // 能进入该循环，说明 这个 parent 只少有一个孩子。
            while(child < len){
        
                // 获取 左右孩子的最大值
                if(child+1 < len &&this.elements[child] < this.elements[child+1]){
        
                    child++;
                }
                // 判断 孩子最大值 是否 比  双亲节点 val 值 大
                // 如果大，就需要进行交换
                if(this.elements[child] > this.elements[parent]){
        
                    int tmp = elements[child];
                    elements[child] = elements[parent];
                    elements[parent] = tmp;
    
                    // 见附图
                    parent = child;
                    child = parent * 2 + 1;
                }else{
        
                    break;
                }
            }
        }
    
        // 入队操作
        public void offer(int val){
        
            if(isFull()){
        
                // 扩容
                this.elements = Arrays.copyOf(this.elements,this.elements.length * 2);
            }
            elements[usedSize++] = val;
            //usedSize++;
            shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1
        }
        private void shiftUp(int child){
        
            int parent = (child - 1)/2;
            while(child > 0){
        
                if(this.elements[child] > this.elements[parent]){
        
                    int tmp = this.elements[child];
                    this.elements[child] = this.elements[parent];
                    this.elements[parent] = tmp;
                    child = parent;
                    parent = (child - 1) / 2;
                }else{
        
                    break;
                }
            }
        }
        // 判断队列满没满
        public boolean isFull(){
        
            return this.usedSize >= this.elements.length;
        }
    
        // 出队操作
        public int poll(){
        
            if(isEmpty()){
        
                throw new RuntimeException("优先级队列为空！");
            }
            int tmp = this.elements[0];
            this.elements[0] = this.elements[this.usedSize -1];
            this.elements[this.usedSize - 1] = tmp;
            this.usedSize--;
            shiftDown(0,usedSize);
            return tmp;
        }
    
        // 判断队列 空不空
        public boolean isEmpty(){
        
            return this.usedSize == 0;
        }
        public int peek(){
        
            if(isEmpty()){
        
                throw new RuntimeException("优先级队列为空！");
            }
            return this.elements[0];
        }
    
    }

## 四、校招 – TopK问题 ##

**问题描述：**

从arr\[1, n\]这n个数中，找出最大的k个数，这就是经典的TopK问题。（从100万中找出最大的k个数）

**栗子：**

从arr\[1, 12\]=\{5,3,7,1,8,2,9,4,7,2,6,6\} 这n=12个数中，找出最大的k=5个。

![在这里插入图片描述][5b379626f239426dbaeaf6ca5d56f307.png]  
**总结**

> 1、如果求前K个最大的元素，要建一个小根堆。  
> 2、如果求 前K个最小的元素，要建一个大根堆。  
> 3、如果是求第k大的元素，建一个小堆，小根堆 堆顶的元素就是第k大的元素。  
> 4、如果是求第k小的元素，建一个大堆，大根堆 堆顶的元素就是第k小的元素。

## 五、堆的其他应用-堆排序 ##

> 1、将数据调整为 大根堆、  
> 2、0 下标 与 最后一个未排序的元素进行交换即可。  
> 3、循环上述两个操作，直至 最后一个未排序的元素 下标为 0.。

![在这里插入图片描述][89b0033172d949aba9306966897d7441.png]

/**
         * 堆排序
         */
        public void heapSort(int[] elem){
        
            int last  = usedSize - 1;
            while (last  > 0){
        
                int tmp = elem[0];
                elem[0] = elem[last ];
                elem[last ] = tmp;
                shiftDown1(0,last);
                last --;
            }
        }
    
        /**
         *向下调整
         * @param parent
         * @param len
         */
        public void shiftDown1(int parent,int len){
        
            int child = parent * 2 + 1;// 左孩子
            // 能进入该循环，说明 这个 parent 只少有一个孩子。
            while(child < len){
        
                // 获取 左右孩子的最大值
                if(child+1 < len &&this.elem[child] < this.elem[child+1]){
        
                    child++;
                }
                // 判断 孩子最大值 是否 比  双亲节点 val 值 大
                // 如果大，就需要进行交换
                if(this.elem[child] > this.elem[parent]){
        
                    int tmp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = tmp;
                    
                    parent = child;
                    child = parent * 2 + 1;
                }else{
        
                    break;
                }
            }
        }

[492b11e94c044a26a178f8adb21810ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2b7b15539e0847efb33440136f63526f.png
[5b500fd24f014af2a1ab5f369e58ff1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a849de56316c4b809c2b5383d8248143.png
[7447f2dae313445a9974191ec41454cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/272d1d32d97b4ae99eccf46d31064c82.png
[9b212bcde589435d9c1fc3ea7ae5274a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/134e485e9b9d4b139161e7aea9676d0a.png
[b2ae1cbb3ed14bab93087912710b26b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6a997296e57547a7806b21636c436ce6.png
[06dc943c35854e0682538fb5126f4cbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c91fd9d1a05c445faaca4ef6eb332b99.png
[caafefdeab704c7881f3f5e97cc5c0a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a2196df6f4774dc08d7e828bb1d61739.png
[d743502b629d4e95a67d768961691f37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6e1039229b484e63a6678d38c9a3b8a4.png
[56d50e76407642379076b212783e1f50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1c8d5c74724a4afaa3bc8a851cf3ab08.png
[Link 1]: https://blog.csdn.net/DarkAndGrey/article/details/122764801
[O_n]: https://www.zhihu.com/question/20729324
[6360b11a729e4b6e95e80b95d15ce964.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5b31b45697cb4c38a3b9a364149efd7b.png
[b7350dee53164d6cb18a012e9be1a898.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f1ffa5bd3c4b488aa483d64fc6b76b25.png
[1154919636394c89ae8b52304897d5e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d2b3e45e460644aab2b3b4e200b4dc56.png
[e17a197224924452b87f59d59ca0dc4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c633f99ba49642f6822695d995fffd9d.png
[cfc68770b67a4606a2dae315a034d19a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4979ea2853a2406082171aad45e79a6f.png
[5b379626f239426dbaeaf6ca5d56f307.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/05d0fc0bfb5c4387865f567332950ca3.png
[89b0033172d949aba9306966897d7441.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c3d3dc1eeb2749a3a019133fe0fff1c1.png