域客士单页网站,模板网站与定制开发网站的区别,学校网站免费建设,id怎么转wordpress一、优先级队列
① 什么是优先级队列#xff1f;
在此之前#xff0c;我们已经学习过了队列的相关知识#xff0c;我们知道队列是一种先进先出的数据结构#xff0c;我们还学习过栈#xff0c;是后进先出的…一、优先级队列
① 什么是优先级队列
在此之前我们已经学习过了队列的相关知识我们知道队列是一种先进先出的数据结构我们还学习过栈是后进先出的数据结构这两种数据结构通常能够帮助我们在解题时存储一些数据但是经过一段时间的练习我们应该也能意识到这两种数据结构的缺点不够灵活。
因为在有些情况下我们要存储的数据并非是只存取队头或者队尾有时我们还想使数据拥有一种排序的规律使得我们能够随时取出和存入按照这种规律下优先级较高的数据而想要实现这一点即便是栈与队列两者的结合双端队列都是无法轻易办到的。 比如有时考试我们会按照学生的成绩进行分配考场想在一个考场中提出或者放入一个学生就要根据他的考试成绩来判断。 于是——优先级队列(PriorityQueue)出现了
二、优先级队列的模拟实现
优先级队列是一种能够按照指定的排序方式自动将数据存到合理的位置的数据结构。它的底层实际上就是通过类似二叉树的结构来实现的~
优先级队列可以分为两种 大根堆(这棵二叉树中每棵树的根节点都比它左右子树的根节点大) 小根堆(这棵二叉树中每棵树的根节点都比它左右子树的根节点小)
(需要注意的是根总是一棵完全二叉树) 比如此时我们有一组数据为{10712684}那么按照小根堆的形式存储它就是 这样的一颗二叉树那么接下来我们一点点的去探究优先级队列究竟是如何实现的
① 基本框架
(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;}
}
这篇文章我们对优先级队列进行了基本的认识并且自己也尝试着模拟实现了一个大根堆关于优先级队列的后续知识我将在后面的文章中为大家讲解那么这篇文章到这里就结束啦作者能力有限如果有哪里说的不够清楚或者不够准确还请各位在评论区多多指出我也会虚心学习的我们下次再见啦
