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

分类:热门推荐日期:2024-03-28浏览:1评论:0

文章目录

  • 前言
    • 堆
      • 一、什么是堆
      • 二、堆又分为大根堆和小根堆
      • 三、由于堆的逻辑结构被看成完全二叉树，那么我们先来了解一下完全二叉树。
      • 四、堆使用数组还是链表储存数据呢？
      • 五、数组构建二叉树和父子节点之间的定位
      • 六、堆进行的操作
      • 七、实现小根堆
        • 1、堆的初始化
        • 2、堆在数组尾部插入
        • 3、堆在数组头部删除
        • 4、获取堆顶的元素
        • 5、获取堆的元素个数
        • 6、判断堆是否为空
        • 7、堆的销毁
        • 8、总代码一览
        • 堆的应用
          • 一、堆排序
            • 1、原理：
            • 2、代码实现
            • 3、时间复杂度
            • 二、TOP-K问题
            • 堆练习
              • 一、数组中两个元素的最大乘积
              • 一、最小数字游戏

                前言

                1、本文章适合新学和复习用，都是用c语言实现的，包含了堆的讲解、堆的应用、堆的练习。

                2、有图解和代码都注释，放心食用哦

                那么开始：

                堆

                一、什么是堆

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

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

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

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

                大小根堆图：

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

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

                完全二叉树与非完全二叉树图：

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

                我建议使用数组

                数组的优点：

                （1）方便定位，可以通过子节点求父节点，也可以通过父节点求子节点。

                （2）占用空间相对链表小。

                （3）堆的逻辑结构是完全二叉树，完全二叉树使用数组可以实现连续存储，不会浪费多余的空间

                数组的缺点：

                要经常扩容，效率降低。

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

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

                六、堆进行的操作

                a.在尾部插入元素。

                b.在头部删除元素 。

                c.在头部获取元素。

                d.察看堆的元素个数。

                f.判断堆是否为空。

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

                堆与普通队列对比

                七、实现小根堆

                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)图解：

                (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)图解：

                (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#include#include#include
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)图解：

                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;
}

                运行结果：

                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 (iprintf("%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;
}

                运行结果：

                堆练习

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

                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 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 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为底)。

                结束了喔

                最后感谢大家的观看！

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号