当前位置：首页 > 行业知识 > 数据结构 - 堆（优先队列）+ 堆的应用 + 堆练习

行业知识

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

2026-11-13 06:04:26 来源：互联网转载

文章目录

前言

一、什么是堆
二、堆又分为大根堆和小根堆
三、由于堆的逻辑结构被看成完全二叉树，那么我们先来了解一下完全二叉树。
四、堆使用数组还是链表储存数据呢？
五、数组构建二叉树和父子节点之间的定位
六、堆进行的操作
七、实现小根堆

1、堆的初始化
2、堆在数组尾部插入
3、堆在数组头部删除
4、获取堆顶的元素
5、获取堆的元素个数
6、判断堆是否为空
7、堆的销毁
8、总代码一览
堆的应用

一、堆排序

1、原理：
2、代码实现
二、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;//开始下标为0p->size = 0;//开始我们给一个容量为4p->capacity = 4;//申请一个空间大小为4DATATYPE* 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] break;}else{arr[child] = arr[father];child = father; //改变子节点下标father = (child - 1) / 2;//再找父节点下标}}//返回元素arr[child] = tmp;} //断言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=logn-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  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=logn-1（以2为底）

最好的情况：不需要调整

综上：时间复杂度为： O（longN）

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#includetypedef 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;//开始下标为0p->size = 0;//开始我们给一个容量为4p->capacity = 4;//申请一个空间大小为4DATATYPE* 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  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] 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//找左孩子节点和保存数据int father = end;int child = father * 2 + 1;int tmp = arr[father];while (child 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

运行结果：

二、TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

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

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

按照上面的思路来：

(1)前k个最大的所以我们建小堆。

(2)先用数组前k个元素去建小堆，然后与后k-n个元素对比，比堆顶元素大的就将堆顶元素与这个元素交换

代码实现：

//上面是小根堆，我就不复制过来了，和上面的堆代码一样，知道接口就行了void PrintTopK(int* arr, int n, int k){//初始化小根堆pq p;IintQueue(&p);//前k个插入for (int i = 0; i  tmp){Priority_Queue_Pop(&p);Priority_Queue_Push(&p, arr[i]);}}    //打印结果while (!Priority_Queue_Enpty(&p)){int t = Priority_Queue_Top(&p);Priority_Queue_Pop(&p);printf("%d \n", t);}}void TestTopk(){int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));//初始话10000个数for (size_t i = 0; i  运行结果：
 堆练习
 一、数组中两个元素的最大乘积
 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);}    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;}

上一篇：揭秘改版背后亮点！众人帮最新变革深度解析！

下一篇：揭秘跑分测试真相，速度与性能的终极对决！

行业知识

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

文章目录

前言

堆

一、什么是堆

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

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

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

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

六、堆进行的操作

七、实现小根堆

1、堆的初始化

2、堆在数组尾部插入

3、堆在数组头部删除

4、获取堆顶的元素

5、获取堆的元素个数

6、判断堆是否为空

7、堆的销毁

8、总代码一览

堆的应用

一、堆排序

1、原理：

二、TOP-K问题

堆练习

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

最新文章

图文

热门标签

友情链接