数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习

这篇具有很好参考价值的文章主要介绍了数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

1、本文章适合新学和复习用,都是用c语言实现的,包含了堆的讲解、堆的应用、堆的练习。
2、有图解和代码都注释,放心食用哦

那么开始:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

一、什么是堆

堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组。

二、堆又分为大根堆和小根堆

大根堆:父节点大于左右孩子节点 。
小根堆:父节点小于左右孩子节点。

大小根堆图:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

三、由于堆的逻辑结构被看成完全二叉树,那么我们先来了解一下完全二叉树。

完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉树与非完全二叉树图:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

四、堆使用数组还是链表储存数据呢?

我建议使用数组
数组的优点:

(1)方便定位,可以通过子节点求父节点,也可以通过父节点求子节点。
(2)占用空间相对链表小。
(3)堆的逻辑结构是完全二叉树,完全二叉树使用数组可以实现连续存储,不会浪费多余的空间

数组的缺点:

要经常扩容,效率降低。

利大于弊,所以数组是一个很好的选择。

五、数组构建二叉树和父子节点之间的定位

数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

六、堆进行的操作

a.在尾部插入元素。
b.在头部删除元素 。
c.在头部获取元素。
d.察看堆的元素个数。
f.判断堆是否为空。

这些操作是不是很熟悉捏,其实这些操作和队列是一样的,但是a,b,d这些核心操作和普通队列是完全不一样的,因为插入和删除利用了堆来实现使最大元素(大根堆)或者最小元素(小根堆)放到顶部,取元素的时候取的是最大或者最小的元素,这使队列不在是先进先出,而是大元素或者小的元素先出,又因为堆的效率很高,所以我们也将其称为最高效的优先队列。

堆与普通队列对比
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

七、实现小根堆

1、堆的初始化

开始对堆的结构体的成员进行初始化,如数组容量,数组大小,申请空间。

堆的结构体:

//定义数据类型
typedef int DATATYPE ;
//堆结构体
typedef struct priority_queues
{
	//数组
	DATATYPE* arr;
	//大小  指向的是有数据后的一个位置
	int size;
	//容量
	int capacity;
}pq;

对堆结构体的初始化:

//初始化
void IintQueue(pq* p)
{
	//断言判断
	assert(p);

     p->arr = NULL;
	//开始下标为0
	p->size = 0;
	//开始我们给一个容量为4
	p->capacity = 4;
	//申请一个空间大小为4
	DATATYPE* tmp = (DATATYPE*)realloc(p->arr, sizeof(DATATYPE) * p->capacity);
	//判断是否申请成功
	if (tmp == NULL)
	{
		printf("申请失败");
		exit(-1);
	}
	p->arr = tmp;
}
2、堆在数组尾部插入

(1)堆在插入元素是一个核心的操作就是要进行调整,进行建小根堆使最小的元素调整到堆顶的位置。
(2)那么如何建小根堆呢?
我们接下来学习一个方法:向上调整法

那么向上调整法是从哪里开始调整呢?答案是每一个新插入的元素。
第一步:利用孩子的下标(插入数据的下标)(child) 找到父节点的下标(father):father = (child-1) / 2
第二步:保存孩子的元素(tmp)
第三步:用孩子节点的元素和父节点元素对比,若孩子的元素比父亲的大就直接打破,调整结束,若孩子节点的元素比父亲节点的元素小就将父节点的元素节点赋给孩子节点并child = father 让之前父节点的位置作为新孩子下标继续寻找下一个父节点的下标:father = (child-1) / 2, 以此往上调整直到遇到比tmp大的父节点或者child = 0(没有父节点)时调整结束。

(3)图解:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

(4)代码实现:

//向上调整
void AdjustUpwards(DATATYPE* arr, int child)
{
     //父节点下标
	int father = 0;
	father = (child - 1) / 2;
	//保存插入元素
	DATATYPE tmp = arr[child];

	while (child >0)
	{
		if (arr[father] <= tmp)
		{
			break;
		}
		else
		{
			arr[child] = arr[father];
			child = father; //改变子节点下标
			father = (child - 1) / 2;//再找父节点下标
		}
	}
	//返回元素
	arr[child] = tmp;
}

(5)接下来就是插入元素:将元素插入到尾部,并进行调整。
代码实现:

//插入元素
void Priority_Queue_Push(pq* p, DATATYPE val)
{
 	//断言
	assert(p);

	//判断是否满了
	if (p->size == p->capacity)
	{
		DATATYPE* tmp = (DATATYPE*)realloc(p->arr, sizeof(DATATYPE) * p->capacity * 2);
		if (tmp == NULL)
		{
			printf("申请失败");
			exit(-1);
		}
		p->arr = tmp;
		p->capacity = p->capacity * 2;
	}
	
	//插入数据
	p->arr[p->size] = val;
	p->size++;

	//调整
	AdjustUpwards(p->arr, p->size-1);
	
}

经过上述步骤之后,堆顶的数据就是整个堆中最小的元素了
(6)插入操作的时间复杂度

最坏的情况:从底位置到0 ,走h(层次高度), n(数组大小)=2^h(层次高度)-1;所以h=h=log(n+1)(以2为底)
最好的情况:不需要调整
综上:时间复杂度为: O(longN)

3、堆在数组头部删除

(1)怎么样将头部元素删除呢?,我们是用数组最后的一个元素将第一个元素覆盖即arr[0] =arr[size-1],并且size–,但是这样就会破坏掉我们的堆,因此我们还要学习另一个方法去重新调整堆,这个方法就向下调整法。
(2)向下调整法 向下调整法顾名思义就是向下调整堆,那么从哪里向下呢?答案是:从父节点向下。
第一步:利用需要调整的下标作为父节点下标,找到左右孩子节点的下标。
第二步:保存该父节点下标的元素(tmp)
第三步:先找到左右孩子中元素大小最小的,再将其与tmp对比,若是tmp小于孩子节点(左或右孩子)元素,arr[father] =tmp,然后结束调整,若tmp大于孩子节点元素,就将孩子节点的元素赋给父节点位置,再改变父节点下标,使孩子节点的下标作为父节点下标,再重新寻找新的孩子下标(arr[father] = arr[child] , father = child ,child = father*2+1 或 child = father*2+2),直到遇到比tmp大的孩子节点元素(左或右孩子)时或者child >size-1时结束调整。

(3)图解:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言
(4)代码实现:

//向下调整
void Build_Biles(DATATYPE* arr, int father,int size)
{
	//找左孩子节点和保存数据
	int child = father * 2 + 1;
	int tmp = arr[father];

	while (child < size)
	{
		//找最小那个孩子节点
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}

		//对比
		if (tmp > arr[child])
		{
			arr[father] = arr[child];
			father = child;
			child= father * 2 + 1;
		}
		else
		{
			break;
		}
	}

	//返回元素
	arr[father] = tmp;
}

(5)删除操作,代码实现:

//弹出数据
bool Priority_Queue_Pop(pq* p)
{
	assert(p);

	//为空无法删除
	if (p->size == 0)
	{
		return false;
	}
	//只有一个元素时,无需调整
	else if (p->size == 1)
	{
		p->size--;
	}
	//存在多个元素时,需要调整
	else
	{
		p->arr[0] = p->arr[p->size - 1];
		p->size--;
		//调整
		Build_Biles(p->arr, 0, p->size);
	}
	
	return true;
}

经过上述步骤之后,数组调整为小堆
(6)删除操作的时间复杂度

最坏的情况:从0位置到底,走h(层次高度), n(数组大小)=2^h(层次高度)-1;所以h=log(n+1)(以2为底)
最好的情况:不需要调整
综上:时间复杂度为: O(logN)

4、获取堆顶的元素

通过判断堆如果不为空就可以返回堆顶元素,要是为空就返回-1,堆顶元素就是下标为 0 的位置,并且该元素是整个堆最小的元素。

代码实现:

//返回数据
DATATYPE Priority_Queue_Top(pq* p)
{
	assert(p);
     //判断是否为空
	if (p->size == 0)
	{
		return -1;
	}

	return p->arr[0];
}
5、获取堆的元素个数

直接返回结构体中的size即可。

代码实现:

//返回元素个数
int Priority_Queue_Size(pq* p)
{
	assert(p);
	return p->size;
}
6、判断堆是否为空

通过判断结构体中的size是否为0即可判断是否为空了。

代码实现:

//判断是否为空
bool Priority_Queue_Enpty(pq* p)
{
	assert(p);
	
	return p->size == 0;
}
7、堆的销毁

对数组进行释放,初始化结构体其他成员。

//销毁
void Priority_Queue_Destroyed(pq* p)
{
	assert(p);

	//释放数组
	free(p->arr);
	p->arr = NULL;
	//初始化成员
	p->capacity = 0;
	p->size = 0;
}
8、总代码一览

priority_queue.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int DATATYPE ;
//结构体
typedef struct priority_queues
{
	//数组
	DATATYPE* arr;
	//大小
	int size;
	//容量
	int capacity;
}pq;

//向下调整
void Build_Biles(DATATYPE* arr, int begin, int end);

//向上调整
void AdjustUpwards(DATATYPE* arr, int begin);

//初始化
void IintQueue(pq *p);

//插入元素
void Priority_Queue_Push(pq *p, DATATYPE val);

//弹出数据
bool Priority_Queue_Pop(pq* p);

//返回队头数据
DATATYPE Priority_Queue_Top(pq* p);

//判断是否为空
bool Priority_Queue_Enpty(pq* p);

//返回元素个数
int Priority_Queue_Size(pq* p);

//销毁
void Priority_Queue_Destroyed(pq* p);

priority_queue.c

#include "priority_queue.h"
//初始化
void IintQueue(pq* p)
{
	//断言判断
	assert(p);

	p->arr = NULL;
	//开始下标为0
	p->size = 0;
	//开始我们给一个容量为4
	p->capacity = 4;
	//申请一个空间大小为4
	DATATYPE* tmp = (DATATYPE*)realloc(p->arr, sizeof(DATATYPE) * p->capacity);
	//判断是否申请成功
	if (tmp == NULL)
	{
		printf("申请失败");
		exit(-1);
	}
	p->arr = tmp;
}


//向下调整
void Build_Biles(DATATYPE* arr, int father,int size)
{
	//找左孩子节点和保存数据
	int child = father * 2 + 1;
	int tmp = arr[father];

	while (child < size)
	{
		//找最小那个孩子节点
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}

		//对比
		if (tmp > arr[child])
		{
			arr[father] = arr[child];
			father = child;
			child= father * 2 + 1;
		}
		else
		{
			break;
		}
	}

	//返回元素
	arr[father] = tmp;
}

//向上调整
void AdjustUpwards(DATATYPE* arr, int child)
{
	int father = 0;
	father = (child - 1) / 2;
	DATATYPE tmp = arr[child];

	while (child >0)
	{
		if (arr[father] <= tmp)
		{
			break;
		}
		else
		{
			arr[child] = arr[father];
			child = father;
			father = (child - 1) / 2;
		}
	}
	arr[child] = tmp;
}

//插入元素
void Priority_Queue_Push(pq* p, DATATYPE val)
{
	assert(p);

	if (p->size == p->capacity)
	{
		DATATYPE* tmp = (DATATYPE*)realloc(p->arr, sizeof(DATATYPE) * p->capacity * 2);
		if (tmp == NULL)
		{
			printf("申请失败");
			exit(-1);
		}
		p->arr = tmp;
		p->capacity = p->capacity * 2;
	}

	p->arr[p->size] = val;
	p->size++;

	//调整
	AdjustUpwards(p->arr, p->size-1);
	
}

//弹出数据
bool Priority_Queue_Pop(pq* p)
{
	assert(p);

	//为空无法删除
	if (p->size == 0)
	{
		return false;
	}
	//只有一个元素时,无需调整
	else if (p->size == 1)
	{
		p->size--;
	}
	//存在多个元素时,需要调整
	else
	{
		p->arr[0] = p->arr[p->size - 1];
		p->size--;
		//调整
		Build_Biles(p->arr, 0, p->size);
	}
	
	return true;
}

//返回数据
DATATYPE Priority_Queue_Top(pq* p)
{
	assert(p);

	if (p->size == 0)
	{
		return -1;
	}

	return p->arr[0];
}

//判断是否为空
bool Priority_Queue_Enpty(pq* p)
{
	return p->size == 0;
}

//返回元素个数
int Priority_Queue_Size(pq* p)
{
	assert(p);
	return p->size;
}

//销毁
void Priority_Queue_Destroyed(pq* p)
{
	assert(p);

	free(p->arr);
	p->arr = NULL;
	p->capacity = 0;
	p->size = 0;
}

以上就是堆的全部内容了,上面实现的小根堆,要是想实现大根堆的话,就将向下向上调整法的大于小于号改一下即可

堆的应用

一、堆排序

实现升序,要是想实现降序改一下向下调整法的大于小于号即可哦

1、原理:

(1)第一步:先将数组调整为大堆。
(2)用我们上面学的向下调整法来将数组调整为大堆,那么从哪里开始向下调整呢?从第一非叶节点(没有左右孩子)的位置开始到0的位置就完成建堆,求第一个非叶节点公式:father =(size-1-1)/2,size是数组大小。
(3)第三步:大堆使最大元素到堆顶,之后将堆顶元素和数组最后一个元素(假设下标为end)交换就可以将最大元素放到最后了,然后重新建堆(除了第一次,其他是从0下标开始调整即可),最后 end--,再将堆顶元素和堆的倒数第二个元素交换,以此类推直到end<=0,这样就完成排序了

(4)图解:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

2、代码实现
//向下调整
void Build_Biles(DATATYPE* arr, int end,int size)
{
	//找左孩子节点和保存数据
	int father = end;
	int child = father * 2 + 1;
	int tmp = arr[father];

	while (child < size)
	{
		//找最小那个孩子节点
		if (child + 1 < size && arr[child] < arr[child + 1])
		{
			child++;
		}

		//对比
		if (tmp < arr[child])
		{
			arr[father] = arr[child];
			father = child;
			child= father * 2 + 1;
		}
		else
		{
			break;
		}
	}

	//返回元素
	arr[father] = tmp;
}
//交换
void Swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;
}

void  HeapSort(int* arr, int size) {
	//建堆,size-1-1就是除2(求子树公式反过来用,最后减一是因为我们求的是下标)
	for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
		Build_Biles(arr, i, size);
	}
	int ned = size - 1;
	//最后一个下标位置开始,和下标为0的元素交换,一直交换下去,并且交换一次就调整一次
		//当ned==1之后再进行一次交换就算排好了,此时调整算法不会奏效了
	while (ned >0) {
		Swap(&arr[0], &arr[ned]);
		Build_Biles(arr, 0, ned);//重新调整
		ned--;
		
	}
}
int main()
{
	int arr[] = { 1,5,3,2,4 };
	HeapSort(arr, 5);
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

运行结果:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

3、时间复杂度

第一步建堆花O(N).
第二步交换调整花O(N logN(以2为底))。
所以时间复杂度可以看成O(NlogN)。

二、TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

  1. 用数据集合中前K个元素来建堆
    前k个最大的元素,则建小堆
    前k个最小的元素,则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

时间复杂度:
建堆 O(K)。
筛选 O((N-K)logK)。(以2为底)
所以时间复杂度为:K+(N-K)logK。

假设我们要求在n=10000整形元素中求前k=10最大的。

按照上面的思路来:
(1)前k个最大的所以我们建小堆。
(2)先用数组前k个元素去建小堆,然后与后k-n个元素对比,比堆顶元素大的就将堆顶元素与这个元素交换

代码实现:

//向下调整
void Build_Biles(DATATYPE* arr, int end,int size)
{
	//找左孩子节点和保存数据
	int father = end;
	int child = father * 2 + 1;
	int tmp = arr[father];

	while (child < size)
	{
		//找最小那个孩子节点
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}

		//对比
		if (tmp > arr[child])
		{
			arr[father] = arr[child];
			father = child;
			child= father * 2 + 1;
		}
		else
		{
			break;
		}
	}

	//返回元素
	arr[father] = tmp;
}
//交换
void Swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;
}


void PrintTopK(int* arr, int n, int k)
{
	//建堆
   for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
		Build_Biles(arr, i, k);
	
	//k-n进行对比,筛选
	for (int i = k; i < n; i++)
	{
			//存在更大的就先删除堆顶在插入
			if (arr[i] > arr[0])
			{
				swap(&arr[i],&arr[0]);
				Build_Biles(arr, 0, k);
			}
	}
    
	//打印结果
	int i=0;
	while (i<k)
	{
		printf("%d \n", arr[i]);
		i++;
	}

}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	//初始话10000个数
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//设置10最大的数
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}
int main()
{
	TestTopk();
	return 0;
}

运行结果:
数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习,数据结构,c语言,数据结构,算法,经验分享,开发语言

堆练习

一、数组中两个元素的最大乘积

1、题目链接:数组中两个元素的最大乘积
2、题目描述:

给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。

3、例子:

示例 1:
输入:nums = [3,4,5,2] 。
输出:12 。
解释:如果选择下标 i=1 和 j=2(下标从 0开始),则可以获得最大值,(nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12 。

4、思路:

(1)其实这题很简单就是排序然后取最大的两个数即可,但是我们尝试用堆去解决这个问题。
(2)用堆的话我们要构建大根堆,可以将数组中的元素全部插入到堆中,然后取堆顶的元素,然后再删除,再取即可拿到最大的两个元素了。

5、代码实现:



//上面的是堆,下面才是主要部分



int maxProduct(int* nums, int numsSize) {
	//初始化
    pq q;
    IintQueue(&q);
    //将全部元素插入
    for(int i=0;i<numsSize;i++)
    {
        Priority_Queue_Push(&q,nums[i]);
    }
    //取两个元素
    int tmp1=Priority_Queue_Top(&q);
    Priority_Queue_Pop(&q);
    int tmp2=Priority_Queue_Top(&q);
    Priority_Queue_Pop(&q);

    //释放堆
    Priority_Queue_Destroyed(&q);
    
    return (tmp1-1)*(tmp2-1);
}

6、时间复杂度为:O(NlogN) (以2为底)。

一、最小数字游戏

1、题目链接:最小数字游戏
2、题目描述:

你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ,同时还有一个空数组 arr 。Alice 和 Bob决定玩一个游戏,游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下:
每一轮,Alice 先从 nums 中移除一个 最小 元素,然后 Bob 执行同样的操作。 接着,Bob 会将移除的元素添加到数组 arr 中,然后 Alice 也执行同样的操作。 游戏持续进行,直到 nums 变为空。 返回结果数组 arr 。

3、例子:

示例 1:

输入:nums = [5,4,2,3]
输出:[3,2,5,4]
解释:第一轮,Alice 先移除 2 ,然后 Bob 移除 3 。然后Bob 先将 3 添加到 arr 中,接着 Alice 再将 2 添加到 arr 中。于是 arr = [3,2] 。第二轮开始时,nums = [5,4] 。Alice 先移除 4 ,然后 Bob 移除 5 。接着他们都将元素添加到 arr 中,arr变为 [3,2,5,4] 。

4、思路:

(1)这一题也是可以通过排序,然后再取对应的元素进新数组里的,还是一样我们用堆做。
(2)因为是找小的元素先,所以我们建小根堆,再通过建全部元素插入到堆里,每轮取出两个元素,取第一个元素先保存,再删除,接着取第二个元素,保存,再删除,然后将第二个取出的元素放进数组,再将第一个取得元素放进,数组,一直循环这个操作直到堆为空即可。

5、代码实现:


//上面是小根堆,就不写了

int* numberGame(int* nums, int numsSize, int* returnSize) {
    int *arr=(int*)malloc(sizeof(int)*numsSize);

	//初始化对象
    pq q;
    IintQueue(&q);
    //插入
    for(int i=0;i<numsSize;i++)
    {
        Priority_Queue_Push(&q,nums[i]);
    }
    
    //i控制数组下标
    int i=0;
    while(!Priority_Queue_Enpty(&q))
    {
      //每轮取两个数
        int tmp1=Priority_Queue_Top(&q);
        Priority_Queue_Pop(&q);
        int tmp2=Priority_Queue_Top(&q);
        Priority_Queue_Pop(&q);
        arr[i++]=tmp2;
        arr[i++]=tmp1;
    }
    //释放
    Priority_Queue_Destroyed(&q);

    *returnSize=numsSize;
    return arr;
}

6、时间复杂度为:O(NlogN) (以2为底)。

结束了喔

最后感谢大家的观看!文章来源地址https://www.toymoban.com/news/detail-838512.html

到了这里,关于数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——堆的应用

    堆结构主要有两个应用:1、堆排序 2、topK问题 现实中,排序是非常常见的,比如排序班级同学的各科分数,购物时,商品会按销量,价格,好评数等进行排序。相信大家也不喜欢再购物筛选时,加载半天出不来吧!一个好的排序用的时间会大大减少,改善用户的体验。堆排

    2024年04月10日
    浏览(77)
  • 优先队列----数据结构

    不知道你玩过英雄联盟吗?英雄联盟里面的防御塔会攻击离自己最近的小兵,但是如果有炮车兵在塔内,防御塔会优先攻击炮车(因为炮车的威胁性更大),只有没有兵线在塔内时,防御塔才会攻击英雄。所以你可以得出优先级:距离最近的炮车  炮车 距离最近的小兵 小兵

    2024年02月06日
    浏览(32)
  • 「数据结构」优先级队列

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 优先级队列底层是用堆实现的 ,关于堆的实现,之前的文章已经详细介绍过了,文章链接:二叉树1:堆的实现 方法 功能 PriorityQueue() 创建一个空的优先级队列,默认容量是11 PriorityQueue(int i

    2024年02月20日
    浏览(42)
  • 数据结构之堆的应用

    在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。 对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。 目录 1.top k问题(优质筛选问题) 2.堆排序 1.向

    2024年02月08日
    浏览(50)
  • 【数据结构】堆的实现及应用

    简单不先于复杂,而是在复杂之后 。 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系

    2024年02月21日
    浏览(46)
  • 数据结构-优先级队列(堆)

    文章目录 目录 文章目录 前言 一 . 堆 二 . 堆的创建(以大根堆为例) 堆的向下调整(重难点)  堆的创建  堆的删除 向上调整 堆的插入 三 . 优先级队列 总结 大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列 堆(Heap)是一种基于完全二叉树的数据结构,具有

    2024年02月08日
    浏览(48)
  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(40)
  • 【数据结构】优先级队列——堆

    🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧【数据结构】非线性结构——二叉树🎈🎈🎈🎈🎈 前面介绍过队列,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能

    2024年04月14日
    浏览(59)
  • 数据结构:优先级队列(堆)

    队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列。 在这种情况下, 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数据结构就是 优先级

    2024年02月08日
    浏览(41)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包