快捷搜索:  朋友圈  as  伪静态  次数  响应式  虎牙  浏览数  anniu

【数据结构和算法】超多图解,超详细,堆详解


作者Linux猿

简介博客专家华为云享专家Linux、C/C、面试、刷题、算法尽管咨询我关注我有问题私聊

关注专栏图解数据结构和算法 优质好文持续更新中……

欢迎小伙伴们点赞、收藏⭐、留言


目录

一、什么是堆

二、堆排序

✨2.1 算法原理

✨2.2 算法步骤

✨2.3 实例演示

✨2.4 代码实现

✨2.5 堆调整原理

三、实例讲解

✨3.1 求第 k 大元素

3.1.1 算法思路

3.1.1 代码实现

✨3.2 求前 k 高频率的元素

3.2.1 算法思路

3.2.2 代码实现

四、总结


一、什么是堆

堆属于二叉树的一种它是一棵完全二叉树。堆有大顶堆和小顶堆之分大顶堆是任意节点大于其左右子节点小顶堆是任意节点大于其左右子节点如下所示

图1 大顶堆

 在上图中每个节点的值都大于左右孩子节点的值例如25 大于 13 和 1013 大于 2 和 8 等。

使用上面的数据来构建一个小顶堆如下所示

图2 小顶堆

 在上图的小顶堆中 每个节点都小于左右孩子节点左右孩子节点谁大谁小并没关系重点是不能比父节点大可以看到2 比孩子节点 8 和 7 都小8 比孩子节点 13 和 25 都小。

我是分割线

二、堆排序

这里以大顶堆为例进行讲解。

✨2.1 算法原理

将待排序元素组成一个大顶堆每次取出堆顶元素堆顶是最大的元素让最后一个元素成为堆顶节点重新调整堆让其成为大顶堆再次交换堆顶元素直到所有元素都有序从而实现对数据的排序。

✨2.2 算法步骤

1将待排序元素构建一个大顶堆

2最后一个节点与根节点交换此时不再是大顶堆

3将堆重新调整堆为大顶堆

4重复步骤 2 ~ 3直到所有元素都有序。

✨2.3 实例演示

下面来看一个实例。

假设有 A[ ] {10, 8, 9, 2, 13, 7, 25}这里以大顶堆为例实现从小到大排序。

1初始堆如下所示

图 初始堆

 2将待排序元素构建成一个大顶堆如下所示

图 构建大顶堆

 3将节点 9 与 节点 25 交换交换后如下所示

图 交换节点 9 和 25

 4标记为红色的节点表示已经有序不再参与排序这时候堆不满足大顶堆重新调整堆为大顶堆调整后如下所示

图 重新调整为大顶堆

 5将节点 13 与 7 交换交换后如下所示

图 交换节点 7 和 13

 6交换后此时的堆不再是大顶堆重新调整为大顶堆调整后如下所示

图 调整堆

 7交换节点 10 与 8交换后如下所示

图 交换节点10 和 8

 8此时堆不再是大顶堆重新调整为大顶堆如下所示

图 调整堆

 9交换节点 9 和 2交换后如下所示

图 交换 9 和 2

 10将堆重新调整为大顶堆如下所示

图 调整大顶堆

 11交换 8 和 7 的值如下所示

图 交换 8 和 7

 12将堆调整为大顶堆可以看到当前堆已是大顶堆然后交换节点 2 和 7如下所示

图 交换节点 7 和 2

 13此时整个对从上到下从左到右是递增的实际在数组中存储是这样的

图 数组中的位置

 在上图中节点下面的数字表示节点在数组中的位置一般是从下标 1 开始存储因为这样方便计算父节点和子节点之间的关系如下所示

1左孩子节点的下标 父节点的下标 * 2

2右孩子节点的下标 父节点的下标 * 2 1

✨2.4 代码实现

#include iostreamusing namespace std;//向下调整堆, 从 idx 节点开始往下调整void adjustHeap(int a[], int idx, int Len){    while(idx*21  Len) {        int temp  idx*2  1;        if(temp1  Len  a[temp1]  a[temp]) {            temp;        }        if(a[idx]  a[temp]) {            swap(a[idx], a[temp]);            idx  temp;        } else break;    }}/* * 堆排序 * g[] : 待排序数组 * n   : 元素个数 */void heapSort(int g[], int n){    //先建立大顶堆    for(int i  (n-1)/2; i  0; --i){        adjustHeap(g, i, n);    }    //排序每次都会有一个元素有序    for(int i  0;i  n; i){        swap(g[0], g[n-i-1]);        adjustHeap(g, 0, n-i-1);    }}int main(){    int n  8;    int g[]  {5, 7, 9, 3, 1, 8, 6, 2};    heapSort(g, n); // 调用堆排序    for(int i  0; i  n; i) {        coutg[i] ;    }    coutendl;    return 0;}

在堆排序的过程中重点是调整堆建立大顶堆的时候heapSort 中第一个 for 循环是从下往上依次调整每个节点使得每个节点都满足大顶堆的条件。

正式排序的时候每次只需要交换根节点重新调整堆即可只需要调整新的根节点因为只有新的根节点不满足堆的定义。

✨2.5 堆调整原理

堆排序中最重要的就是堆的调整了下面就可以下图的为例子进行讲解如下所示

图1 堆调整示意图

 在上图中只有 3 是不符合条件的下面就来调整下 3 节点动图如下所示

图 堆调整动图

 在上图中3 先与 13 交换然后再与 8 交换交换后便成为一个大顶堆。

我是分割线

三、实例讲解

✨3.1 求第 k 大元素

给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。

3.1.1 算法思路

对数组 nums 中的元素进行堆排序因为堆排序可以每次确定一个最大值所以只需要求解到第 k 个最大值即可。如果使用其它排序算法要排序所有元素这就显示出了堆排序的优势并不需要全部排序完才找到第 k 大的元素。

3.1.1 代码实现

#include iostream#include vectorusing namespace std;class Solution {public:    //向下调整堆    void adjustHeap(vectorint nums, int idx, int Len) {        while(idx*21  Len) {            int temp  idx*2  1;            if(temp  1  Len  nums[temp1]  nums[temp]){                temp;            }            if(nums[idx]  nums[temp]) {                swap(nums[idx], nums[temp]);                idx  temp;            } else break;        }    }    int findKthLargest(vectorint nums, int k) {        //先建立大顶堆        int n  nums.size();        for(int i  (n-1)/2; i  0; --i){            adjustHeap(nums, i, n);        }        for(int i  0; i  nums.size(); i) {            coutnums[i] ;        }        coutendl;        //排序        for(int i  0;i  k - 1; i){            swap(nums[0], nums[n-i-1]);            adjustHeap(nums, 0, n-i-1);        }        return nums[0];    }};int main(){    int g[]  {5, 7, 9, 3, 1, 8, 6, 2};    vectorint nums(g, g8);    coutendl;    Solution obj;    int k;    while(cink) {        coutThe k-th largest number is obj.findKthLargest(nums, k)endl;    }    return 0;}

✨3.2 求前 k 高频率的元素

给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按任意顺序 返回答案。 

3.2.1 算法思路

这个题目类似于第一个题目但是需要计算每个整数的频率可以使用 map 进行统计然后就可以使用堆排序求第 k 大了。

3.2.2 代码实现

#include iostream#include vector#include mapusing namespace std;class Solution {public:    //向下调整堆    void adjustHeap(vectorpairint, int  nums, int idx, int Len) {        while(idx*21  Len) {            int temp  idx*2  1;            if(temp  1  Len  nums[temp1].second  nums[temp].second){                temp;            }            if(nums[idx].second  nums[temp].second) {                swap(nums[idx], nums[temp]);                idx  temp;            } else break;        }    }    vectorint topKFrequent(vectorint nums, int k) {        mapint, intmp;        for(int i  0; i  (int)nums.size(); i) {            mp[nums[i]];        }        vectorpairint, int hep;        mapint, int::iterator it;        for(it  mp.begin(); it ! mp.end(); it) {            hep.push_back(pairint, int(it-first, it-second));        }        //先建立大顶堆        int n  hep.size();        for(int i  (n-1)/2; i  0; --i){            adjustHeap(hep, i, n);        }        //排序        vectorint ans;        for(int i  0;i  k - 1; i){            ans.push_back(hep[0].first);            swap(hep[0], hep[n-i-1]);            adjustHeap(hep, 0, n-i-1);        }        ans.push_back(hep[0].first);        return ans;    }};int main(){    int g[]  {1, 2, 2, 1, 3, 8, 8, 1};    vectorint nums(g, g8);    coutendl;    Solution obj;    int k;    while(cink) {        vectorint ans  obj.topKFrequent(nums, k);        for(int i  0; i  ans.size(); i) {            coutans[i] ;        }        coutendl;    }    return 0;}

我是分割线

 

四、总结

堆排序经常用在求第 K 大上因为堆的每次调整根元素一定是最大/小的元素。

欢迎关注下方公众号获取更多福利等你来领比心

您可能还会对下面的文章感兴趣: