《黑马程序员》- 优先队列(最大or最小)
2021/7/7 1:05:06
本文主要是介绍《黑马程序员》- 优先队列(最大or最小),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
定义
优先队列,顾名思义,队列中的元素有优先级。
优先队列按照其作用不同,可以分为以下两种:
(1)最大优先队列:可以获取并删除队列中最大的值
最大优先队列:无论入队的顺序,当前最大的元素先出列。
(2)最小优先队列:可以获取并删除队列中最小的值
最小优先队列:无论入队的顺序,当前最小的元素先出列。
最大优先队列
堆这种结构是可以方便的删除最大的值,所以可以直接用堆结构实现最大优先队列。 堆结构: https://blog.csdn.net/Amigo_1997/article/details/118441974?spm=1001.2014.3001.5501最小优先队列
也是通过堆的思想来实现,但是之前讲的堆特点如下,可以称为最大堆1. 最大的元素放在数组的索引 1 处。 2. 每个结点的数据总是大于等于它的两个子结点的数据。而最小堆则利用相反的思想,特点如下
1. 最小的元素放在数组的索引 1 处。 2. 每个结点的数据总是小于等于它的两个子结点的数据。
package tree2; public class MinPriorityQueue <T extends Comparable<T>>{ private T[] items; private int N; public MinPriorityQueue(int capacity){ this.items = (T[]) new Comparable[capacity+1]; this.N = 0; } // 获取队列中元素的个数 public int size(){ return N; } // 判断队列是否为空 public boolean isEmpty(){ return N==0; } // 判断堆中索引i处的元素是否小于索引j处的元素 private boolean less(int i, int j){ return items[i].compareTo(items[j])<0; } // 交换堆中的元素值 private void exch(int i, int j){ T tmp = items[i]; items[i] = items[j]; items[j] = tmp; } // 往堆中插入一个元素 public void insert(T t){ items[++N] = t; swim(N); } // 删除堆中最小的元素,并返回这个最小元素 public T delMin(){ T min = items[1]; exch(1,N); N--; sink(1); return min; } // 上浮算法 private void swim(int k){ while(k>1){ if(less(k,k/2)){ // k/2是父节点 exch(k,k/2); } k = k/2; } } // 下沉算法 private void sink(int k){ while(2*k<=N){ // 2*k是左子节点 int min; //索引值 if(2*k+1<=N){ if(less(2*k,2*k+1)){ min = 2*k; }else{ min = 2*k+1; } }else{ min = 2*k; } //判断当前结点和较小值的大小 if(less(k,min)){ break; } exch(k,min); k=min; //这里容易写反 } } }
这篇关于《黑马程序员》- 优先队列(最大or最小)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求