Java-数据结构-优先级队列(堆)

一、优先级队列

① 什么是优先级队列？

在此之前，我们已经学习过了"队列"的相关知识，我们知道"队列"是一种"先进先出"的数据结构，我们还学习过"栈"，是"后进先出"的数据结构，这两种数据结构通常能够帮助我们在解题时存储一些数据，但是经过一段时间的练习，我们应该也能意识到这两种数据结构的缺点："不够灵活"。

因为在有些情况下，我们要存储的数据并非是只存取队头或者队尾，有时我们还想使数据拥有一种排序的规律，使得我们能够随时取出和存入"按照这种规律下，优先级较高的数据"，而想要实现这一点，即便是"栈"与"队列"两者的结合"双端队列"，都是无法轻易办到的。

📚 比如：有时考试我们会按照学生的成绩进行分配考场，想在一个考场中提出或者放入一个学生，就要根据他的考试成绩来判断。

于是——优先级队列(PriorityQueue)出现了

二、优先级队列的模拟实现

优先级队列是一种能够按照指定的排序方式，自动将数据存到合理的位置的数据结构。它的底层实际上就是通过类似二叉树的结构来实现的~

优先级队列可以分为两种：

📕 大根堆(这棵二叉树中，每棵树的根节点都比它左右子树的根节点大)

📕 小根堆(这棵二叉树中，每棵树的根节点都比它左右子树的根节点小)

(需要注意的是：根总是一棵完全二叉树)

📚 比如：此时我们有一组数据为{10，7，12，6，8，4}，那么按照小根堆的形式存储它，就是：

这样的一颗二叉树，那么接下来我们一点点的去探究，优先级队列究竟是如何实现的：

① 基本框架

(java默认的优先级队列为小根堆，所以我们这里尝试模拟实现一个大根堆)

与之前一些数据结构的模拟实现较为类似，由于"堆"是一棵完全二叉树，所以这里我们的模拟实现就不再使用链表了。而是直接使用数组进行实现(通过层序遍历的顺序)，所以我们需要最基本的一个整数数组elem，还需要一个记录有效数据个数的usedSize~

import java.util.*;public class MyHeap {public int[] elem;public int usedSize;public MyHeap() {}//对elem进行初始化public void init(int[] array) {}//创建一个优先级队列public void createHeap(int[] array) {}//向下调整private void shiftDown(int root,int len) {}//元素入队(不破坏优先级队列结构)public void push(int val) {}//向上调整private void shiftUp(int child) {}//判满public boolean isFull() {}//出队public void pollHeap() {}//判空public boolean isEmpty() {}//获取队顶元素public int peekHeap() {}
}

② 初始化elem

📚 思路提示：

该方法用于我们先将数组存入elem中，以便我们后续的操作，我们只需要将数组中的元素存入elem，并且在初始化elem途中，适时的对elem进行扩容即可~

📖 代码示例：

    //对elem进行初始化public void init(int[] array) {int len = array.length;for (int i = 0; i < len; i++) {if (isFull()) {elem = Arrays.copyOf(elem, elem.length * 2);}elem[i] = array[i];usedSize++;}}

    //判满public boolean isFull() {return usedSize == elem.length;}

③ 堆的向下调整

📚 思路提示：

想要创建一个大根堆，就需要我们上面提到的大根堆性质"每棵树的根节点都比它左右子树的根节点大"

而想要使我们的elem中的元素也遵从这种规律，我们就要知道应该如何去对堆中的元素位置进行调整。其实还是比较简单的：

📚 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有结点从0开始编号，则对于序号为i的结点有以下性质：

📕 若孩子节点下标为 i ，那么父亲结点为 (i - 1) / 2 [i > 0]

📕 若父亲节点下标为 i ，那么左孩子节点为 2 * i + 1 [2i + 1 < n]，右孩子节点为 2 * i + 2  [2i + 2 < n]

📕 首先，将需要调整的元素下标记作parent

📕 如果parent存在左孩子，则通过公式，算出parent的左孩子结点child

📕 如果有两个孩子结点，则将孩子结点标记为值最大的孩子

📕 判断孩子结点与父亲结点的大小，如果孩子更大，则交换孩子与父亲结点(大根堆)

📕 如果交换了结点，则将parent标记为child，再重新求child

⭐ 图示：

📖 代码示例：

    //向下调整private void shiftDown(int parent,int len) {int child = parent * 2 + 1;while(child < len){//判断是否有右孩子,并且右孩子是否更大if(child + 1 < len && elem[child + 1] > elem[child]){child++;}if(elem[child] > elem[parent]){swap(elem,child,parent);parent = child;child = parent * 2 + 1;}else {break;}}}

    public void swap(int[] arr,int i,int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

④ 堆的创建

📚 思路提示：

我们刚刚所实现的"向下调整"，其实就是为了这一步我们成功的构建出一个"大根堆"而进行的铺垫

我们可以注意到，在上面的"向上调整"中，我们每一次进行交换，其实就是创建出了一个"这三个元素组成的局部大根堆"，而想将整个数组都变成大根堆，我们就可以对数组中每一个有子节点的根进行向下调整~

📖 代码示例：

    //创建一个优先级队列public void createHeap() {int len = elem.length;int parent = (elem.length - 1 - 1) / 2;for(int i = parent;i >= 0;i--){shiftDown(i,len);}}

这里或许大家会有一个疑问：为什么从最后一个根节点向上调整，而不是从第一个根节点向下调整？这是因为，两种看似一样的方法，其实时间复杂度相差并不小：

📕 如果从第一个根节点开始向下调整：

对于根节点（位于第 1 层），它可能需要向下调整到叶子节点（第 log n 层），因此调整的时间复杂度是 O(log n)。

对于第 2 层的节点，它们可能需要向下调整到第 log n - 1 层，时间复杂度是 O(log n - 1)。

以此类推，直到叶子节点（不需要调整）。

这种方式的调整，时间复杂度为O(nlogn)

📕 如果从最后一个根节点向上调整：

直接能够越过所有的叶子节点（最好的情况占结点总数一半 + 1）

对于剩余的结点，调整取决于它们的高度，并且越接近根节点，需要调整的高度越低。

这种方式的调整，时间复杂度接近O(n)

⑤ 堆的插入

📚 思路提示：

顾名思义，就是在堆中插入一个元素，但是我们需要注意的是，不论是此刻的插入，亦或是之后我们需要进行的删除，都要保证操作后仍然为大根堆。所以在我们将新的元素插入到堆的末尾后，还要将该元素不断地向上进行调整，直到在某一刻符合大根堆的条件，停止调整。

📕 对堆进行判满，如果堆已满则进行扩容

📕 将新的元素插入堆的末尾，usedSize++

📕 对新元素进行向上调整：

📕 将元素下标标记为child，并且通过公式求出它的parent

📕 如果 parent >= 0 判断child和parent的值，如果child更大，两者进行交换，否则调整结束

(因为在此之前，已经是标准的大根堆，所以不需要进行两个child的判断，只调整目标结点即可)

📕 如果进行了交换，则再将parent = child，然后重新求parent

⭐ 图示：

📖 代码示例：

    //元素入队(不破坏优先级队列结构)public void push(int val) {if(isFull()){elem = Arrays.copyOf(elem, elem.length * 2);}elem[usedSize] = val;shiftUp(usedSize++);}

    //向上调整private void shiftUp(int child) {int parent = (child - 1) / 2;while(parent >= 0){if(elem[child] > elem[parent]){swap(elem,child,parent);child = parent;parent = (child - 1) / 2;}else {break;}}}

⑥ 堆的删除

(注意：堆的删除指的是删除堆顶元素)

📚 思路提示：

想要删除一个堆顶元素，我们首先知道的是"usedSize"需要减一，那么我们由这点思考一下，如果不进行任何操作，首先usedSize--后，我们的堆中实际上消失的是哪个元素？没错，就是堆中的最后一个元素~，但是我们想删除的并不是该元素，而是我们的堆顶元素，简单呀~将这两个元素互换一下不就好了~最后再将新的堆顶元素进行向下调整即可~

📕 首先，判断该堆是否为空，若为空则直接退出该方法

📕 将堆顶元素与堆中最后一个元素进行交换

📕 然后将usedSize--

📕 最后将新的堆顶元素进行向下调整

⭐ 图示：

📖 代码示例：

    //出队public void pollHeap() {if(isEmpty()){return;}swap(elem,0,--usedSize);shiftDown(0,usedSize);}

    //判空public boolean isEmpty() {return usedSize == 0;}

    //获取队顶元素public int peekHeap() {return elem[0];}

完整代码：

import java.util.*;public class MyHeap {public int[] elem;public int usedSize;public MyHeap(){elem = new int[10];}//创建一个大根堆public void creative(int[] arr){for(int i = 0;i < arr.length;i++){if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}elem[i] = arr[i];usedSize++;}}public void doArr(){//最后一个叶子结点的父结点int start = (usedSize - 1 - 1) / 2;for(int i = start;i >= 0;i--){siftDown(i,usedSize);}}//将较大的子节点与父结点交换//向下调整public void siftDown(int parent,int end){//找到父结点的的左子结点int child = parent * 2 + 1;//保证该子结点未越界while(child < end){//查找左右子结点中的最大子结点//(包含了找出最大值后,对右子节点的判断)if(child + 1 < end && 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;}}}//向堆中添加新元素public void offer(int val){if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}elem[usedSize] = val;siftUp(usedSize);usedSize++;}//向上调整public void siftUp(int child){int parent = (child - 1) / 2;while(parent >= 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 int poll(){int oldValue = elem[0];elem[0] = elem[--usedSize];siftDown(0,usedSize);return oldValue;}//将堆排序成从小到大的顺序public void heapSort(){int end = usedSize - 1;while(end > 0){int tmp = elem[end];elem[end] = elem[0];elem[0] = tmp;siftDown(0,end);end--;}}public boolean isFull(){return usedSize >= elem.length;}
}

这篇文章我们对"优先级队列"进行了基本的认识，并且自己也尝试着模拟实现了一个大根堆，关于"优先级队列"的后续知识我将在后面的文章中为大家讲解，那么这篇文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦