优先队列的数据结构,数据结构 优先队列
很久没有更新眼前的数据结构了。这几天一直在做二叉树的题目。对我来说有点难，心里也有点烦躁，所以一直没有和大家分享我的知识。今天我要说的是堆，不太了解。为了我们更好的理解，我用C语言来模拟实现它的基本逻辑。因为这种数据结构是用Java封装的，所以堆被称为优先级队列。我来说说它的用法，看看IEDA的一些源代码。总的来说还是比较难的，但是我相信这么帅的读者一定会掌握的。
开头讲堆的时候，我们不提二叉树。在众多二叉树中，最基本也是最重要的一种叫做完全二叉树。完整的二叉树可以理解为从根节点开始标注。从0开始，每一层按照树的节点从左到右进行标注，不会出现节点跳跃的树。
众所周知，树是一种非线性结构，它的数据存储空间是不连续的。能否有办法让一个完整二叉树中的数据集中化？这是桩的结构。
堆的物理结构是数组堆，堆的逻辑结构是完整的二叉树。如何在树堆中存储数据是序列遍历。我们把数据一层一层放入数组。但是，我们这里就不说数字的遍历了。是我今天在这里讲二叉树，帮助我们理解我们今天的堆，以及如何构建它。
堆堆的性质有许多优良的特性。在说之前，先说一下堆的分类。
有两种桩。
大堆(大根堆)的父节点存储的数据大于子节点存储的数据，小堆(小根堆)的父节点存储的数据小于子节点存储的数据。我们还想谈谈堆的特点。如果我们将根节点的下标标记为0，如果给定一个下标为I的节点，就可以得到它的父节点和子节点(如果有的话)的下标。
家长(i-1)/2左孩子2 i 1右孩子2 i 2堆楼理论知识。我们需要知道这么多。以下是我们的实际操作。我们以搭建一个小桩为例。只要我们学会建小堆，大堆就不在话下了。
我们需要一个结构来帮助我们完成任务。让我们看一看。
#杂注一次
#包含stdio.h
#include assert.h
#包含stdlib.h
#包含stdbool.h
typedef int HPDataTytpe
结构堆
{
HPDataTytpe * elem//指针
size _ t szie//数组的有限元素的数量
size_t容量；//数组的空间大小
};我们要写下面的函数，了解这些函数的原理，就可以掌握堆了。
//初始化堆
void Heap init(Heap * PHP)；
//销毁堆
void Heap destroy(Heap * PHP)；
//数据堆积
void HeapPush(Heap* php，HPDataTytpe val)；
//堆外的数据
void Heap PP(Heap * PHP)；
//确定堆是否为空
bool HeapEmpty(Heap * PHP)；
//向上调整
void adjustUp(HPDataTytpe* elem，int size)；
//向下调整
void adjust down(HPDataTytpe * elem，int size，size _ t root)；初始化堆和销毁堆都很简单，就不说了。我把代码放在下面。
void HeapInit(Heap* php)
{
assert(PHP)；
PHP-elem=NULL；
PHP-capacity=0；
PHP-szie=0；
}void HeapDestroy(Heap* php)
{
assert(PHP)；
免费(PHP-elem)；
PHP-elem=NULL；
PHP-capacity=0；
PHP-szie=0；
}数据堆进堆里这是我们今天的硬菜之一。最好吃的就是里面的向上调整。对于空堆推送(heap * PHP，hpdatatypeval)；函数，我们把数据放在数组的末尾，但是这个数组还必须是一个小堆吗？不，我们需要做一个向上的调整来保持它在一个小堆里。
void HeapPush(Heap* php，HPDataTytpe val)
{
assert(PHP)；
//完整的句子
if (php- capacity==php- szie)
{
size_t newSize=(php- capacity==0)？4:2 *(PHP-capacity)；
HPDataTytpe * pCur=(HPDataTytpe *)realloc(PHP-elem，sizeof(HPDataTytpe)* new size)；
断言(pCur)；
PHP-elem=pCur；
PHP-capacity=new size；
}
PHP-elem[PHP-szie]=val；
adjustUp(php- elem，PHP-szie)；//向上调整
}向上调整当我们的数据进入数组时，它不一定是堆，所以我们必须向上调整，使它仍然是堆。这是向上调整的示意图。
无效交换(HPDataTytpe* pa，HPDataTytpe*pb)
{
断言(pa Pb)；
HPDataTytpe ret=* pa
* pa=* pb
* pb=ret
}
void adjustUp(HPDataTytpe* elem，int size)
{
断言(elem)；
int child=size-1；
int parent=(child-1)/2；
While (child 0) //判断条件很重要。
{
if (elem[child] elem[parent])
{
swap( elem[child]，elem[parent])；//交换这两个数字
}
其他
{
打破；
}
孩子=父母；
parent=(child-1)/2；
}
}通过以上，我们可以建立一个小堆。用代码试试吧
int main()
{
堆堆；
HeapInit(堆)；
HeapPush( heap，3)；
HeapPush( heap，5)；
HeapPush(堆，6)；
HeapPush(堆，10)；
HeapPush(堆，0)；
for(int I=0；I(int)heap . szie；我)
{
printf(%d ，heap . elem[I])；
}
返回0；
}
数据堆学习上面的堆操作，我们初步了解了什么是对=堆，以及如何构建。那么如果我们从反应堆顶部得到数据，我们应该怎么做呢？由于堆的物理结构是一个数组，我们是否可以删除第一个元素，然后仍然为其余的元素构建堆？可以，但是我觉得这次太复杂了。伟大的老板使用以下方法。既然要找到堆顶的元素，是否可以将堆顶的元素和堆尾的元素互换，将数组中的元素个数减1，然后让堆顶的元素下移，使其保持在一个堆中？这是向下调整。
bool HeapEmpty(Heap* php)
{
assert(PHP)；
return PHP-szie==0；
}
void HeapPop(Heap* php)
{
assert(PHP)；
if (HeapEmpty(php))
{
返回；
}
//交换反应器的顶部和尾部
swap( (php- elem[0])，(PHP-elem[PHP-szie-1])；
PHP-szie-；
//向下调整
adjustDown(php- elem，php- szie，0)；
}向下调整堆顶的元素和堆尾的元素。数组元素个数减1，堆顶元素向下调整。
void adjust down(HPDataTytpe * elem，int size，size_t root)
{
断言(elem)；
int parent=root
int child=2 * parent 1；
//判断条件
while(儿童尺寸)
{
//确定哪个孩子更小，左边的孩子还是右边的孩子(如果存在的话)
if(child 1 size elem[child 1]heap type elem[child])
{
孩子；
}
if (elem[child] elem[parent])
{
swap( elem[child]，elem[parent])；
}
其他
{
打破；
}
父母=孩子；
子代=2 *父代1；
}
}测试一下。
int main()
{
堆堆；
HeapInit(堆)；
HeapPush( heap，3)；
HeapPush( heap，5)；
HeapPush(堆，6)；
HeapPush(堆，10)；
HeapPush(堆，0)；
//从堆中取出
HeapPop(堆)；
for(int I=0；I(int)heap . szie；我)
{
printf(%d ，heap . elem[I])；
}
HeapDestroy(堆)；
返回0；
}
对比下调和上调我们来对比一下它们的时间复杂度。
上调的时间复杂度。我们发现数组中的每个元素都参与向上调整。我们从最后一个元素开始，时间复杂度为O(N)logN
向下时间复杂度O(N)
堆排序我们来说说堆排序。给定一个数组，我们如何按升序排列它？之前，我们可以通过冒泡来排序。今天我们来讲一个新的排序方法，堆排序。在讨论这个之前，我们先来看看堆的一些属性。
小堆是所有元素中最小的，大堆是所有元素中最大的。如果按照升序排列，我们需要建立一个大堆。前面我们讲过一个一个的堆。现在来说说如何用数字来堆。我们用两种方法建立一个堆。
使用向上调整来堆积数组。
我来解释一下下面的代码。
为什么我从1开始？
我可以从0开始，但是对于一个元素来说，要构建一个堆，它已经可以是一个堆了，所以没有必要构建。
adjustUp(arr，i1)；
为什么我1？这个就看我个人对上调函数参数的定义了。Mine是传入元素的数量，所以需要i 1。比如，当i=1时，前两个元素叠加。
void HeapSort(int* arr，int len)
{
断言(arr)；
for(int I=1；我len我)
{
adjustUp(arr，i1)；
}
}完整代码
void HeapSort(int* arr，int len)
{
断言(arr)；
//建立一个堆
for(int I=1；我len我)
{
adjustUp(arr，i1)；
}
//堆排序
for(int I=len；I 0；)
{
//交换
int ret=arr[0]；
arr[0]=arr[I-1]；
arr[I-1]=ret；
I-；
adjustDown(arr，I，0)；
}
}使用向下调整构建一堆数组。
前面的上调是用来建桩的，这里用的是下调。
void HeapSort(int* arr，int len)
{
断言(arr)；
for(int parent=(len-1-1)/2；parent=0；父母-)
{
//叶子不需要调整
adjustDown(arr，len，parent)；
}
}
完整代码。
void HeapSort(int* arr，int len)
{
断言(arr)；
for(int parent=(len-1-1)/2；parent=0；父母-)
{
//叶子不需要调整
adjustDown(arr，len，parent)；
}
//堆排序
for(int I=len；I 0；)
{
//交换
int ret=arr[0]；
arr[0]=arr[I-1]；
arr[I-1]=ret；
I-；
adjustDown(arr，I，0)；
}
}测试代码看看。
int main()
{
int arr[]={ 4，2，7，8，5，1，0，6 }；
int SZ=sizeof(arr)/sizeof(arr[0])；
HeapSort(arr，SZ)；
for(int I=0；我SZ；我)
{
printf(%d ，arr[I])；
}
返回0；
}
TopK问题希望看这篇博客的朋友不要再问我TopK问题了。很简单。
TOP-K问题：即寻找数据组合中第一个K的最大或最小元素。一般数据量比较大。
比如：职业10强，世界500强，富豪榜，游戏活跃玩家100强等。
对于Top-K问题，能想到的最简单直接的办法就是排序，但是：如果数据量非常大，排序是不可取的(可能所有的数据都无法一次性加载到内存中)。最好的办法是用堆来解决，
基本想法如下：
找到最上面的k个千里马，建立一个小堆。堆的大小是k，找到最上面的k个最大值，建立一个大堆。堆的大小是k，我们举个例子。
对于3，4，2，6，12，5，6，7，10，求前三个最大值。我们用前三个元素搭建一个桩，然后依次和桩的设置进行对比。如果大于桩顶，则桩顶先出来，再进入桩顶。
下图有错，堆完还得向上调整。其中一个已经被遗忘了。
int* TopK(int* arr，int len，int k)
{
断言(arr)；
int * p=(int *)malloc(sizeof(int)* k)；
断言(p)；
堆堆；
HeapInit(堆)；
for(int I=0；我k；我)
{
HeapPush( heap，arr[I])；
}
for(int I=k；我len我)
{
int ret=HeapPeek(堆)；
if(数组[i] ret)
{
HeapPop(堆)；
HeapPush( heap，arr[I])；
}
}
int I=0；
而(！HeapEmpty(堆))
{
p[i ]=HeapPeek(堆)；
HeapPop(堆)；
}
HeapDestroy(堆)；
返回p；
}
int main()
{
int arr[]={ 3，4，2，6，12，5，6，7，10 }；
int SZ=sizeof(arr)/sizeof(arr[0])；
int k=3；
int* pa=TopK(arr，sz，k)；
for(int I=0；我k；我)
{
printf(%d ，pa[I])；
}
免费(pa)；
pa=NULL
返回0；
}
优先级队列在Java里，堆已经封装好了，叫做优先级队列。让我们一起来看看吧。Java默认建立一个小堆。
公共类TestDemo {
公共静态void main(String[] args) {
PriorityQueue整数priority queue=new priority queue()；
priority queue . add(0)；
priority queue . add(1)；
priority queue . add(2)；
priority queue . add(4)；
priority queue . add(5)；
而(！priorityQueue.isEmpty()) {
system . out . print(priority queue . poll() )；
}
}
}
堆是一种自定义类型。我加入优先队列来谈谈这个问题。Java提供了泛型，这意味着我们可以传入自定义类型。让我们看一看。
班级学生{
公共int age
公共字符串名称；
公共学生(字符串名称，整数){
this.age=年龄；
this.name=name
}
@覆盖
公共字符串toString() {
返回“学生”
年龄=年龄
，name= name \
};
}
}
公共类TestDemo {
公共静态void main(String[] args) {
PriorityQueue学生priority queue=new priority queue()；
PriorityQueue.add(新生(张三，18))；
PriorityQueue.add(新生(李四，10))；
}
}
为何会报错？这里我们想想就会知道，对于堆，我们要是传入的是（同国际组织)国际组织型，直接比较数值就可以了，但是对于自定义类型，我们该如何比较？比较的规则又是什么？这些编译器都无法自动去确定。需要我们来辅助一下
这里有脸肿解决方法
类里面重写比较使用比较器比较仪类里面重写比较对类的侵入性比较强，不推荐
班级学生实施可比学生{
公共年龄
公共字符串名称；
公共学生（字符串名称，整数){
this.age=年龄；
this.name=name
}
@覆盖
公共国际比较（学生o) {
返回这个。年龄-o .年龄；
}
@覆盖
公共字符串toString() {
返回"学生"
年龄=年龄
，name= name \
};
}
}
公共类测试演示{
公共静态void main(String[] args) {
优先级队列学生优先级队列=新优先级队列()；
学生[]学生=新生[2];
学生[0]=新学生(张三,19);
学生[1]=新学生(李四,10);
优先级队列。添加(学生[0])；
优先级队列。添加(学生[1])；
系统。出去。println(优先级队列)；
}
}
使用比较器比较仪可以比较任意的成员变量，推荐
注意O1。年龄-氧气。年龄；是建立小堆，也就是构造器传入的第一个参数是插入的元素
班级学生{
公共年龄
公共字符串名称；
公共学生（字符串名称，整数){
this.age=年龄；
this.name=name
}
@覆盖
公共字符串toString() {
返回"学生"
年龄=年龄
，name= name \
};
}
}
阶级年龄比较仪实现比较器学生{
@覆盖
公共（同Internationalorganizations）国际组织比较（学生o1，学生o2) {
返回O1。年龄-氧气。年龄；
}
}
公共类测试演示{
公共静态void main(String[] args) {
优先级队列学生优先级队列=新优先级队列(新年龄比较器())；
学生[]学生=新生[2];
学生[0]=新学生(张三,19);
学生[1]=新学生(李四,10);
优先级队列。添加(学生[0])；
优先级队列。添加(学生[1])；
系统。出去。println(优先级队列)；
}
}
优先级队列的原理我要带着大家看看想法的源码
我们发现向上调整方法中出现了两个比较方法，比较器！=空是判断条件，我们没有赋值啊？编译器是怎么给比较仪赋值的啊？
实际上这和我们的构造函数有关
## 构造函数不传入参数
构造函数传入构造器
原理
评论0 发布评论
wx604d7ad249574
2022-04-24 16:27
有什么问题可以找我
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。