写点什么

【数据结构与算法】“堆”还能这样用 _ 堆的应用

作者:Dream-Y.ocean
  • 2022 年 9 月 27 日
    广东
  • 本文字数:5102 字

    阅读完需:约 17 分钟

【数据结构与算法】“堆”还能这样用_堆的应用

前情提要


本章节是数据结构堆的应用的相关知识~


接下来我们即将进入一个全新的空间,对代码有一个全新的视角~


以下的内容一定会让你对数据结构有一个颠覆性的认识哦!!!


❗以下内容以C语言的方式实现,对于数据结构来说最重要的是思想哦❗


以下内容干货满满,跟上步伐吧~



💡本章重点

  • 堆排序

  • Top-K 问题



🍞堆的应用

🥐Ⅰ.堆排序

💡堆排序:


  • 本质为选择排序的一种

  • 堆排序便是利用这种数据结构的思想进行排序


✊如果有同学不太熟悉,可点击⌈跳转⌋补充知识再出发呀


🔥 思想:


  • 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完


思考: 如何利用进行排序


  • 假如排升序,我们利用小堆进行排序的话:

  • 我们建好一个小堆后,因为小堆的特性为最小的数在根节点处(最上面),我们便排好升序中的第一个数字

  • 此时我们再继续排剩下的数字,便需要在建堆的时候剔除已经排好的数字,继而将剩下的重新的建堆,选最小的数字

  • 重复上述步骤即可


特别注意:


  • 如果按照上述方法进行排序的话,有两个问题:

  • 🔴第一次建好堆后,在选出最小的数字放到第一个位置紧接着要选出次小的(即进行第二次建堆选数,谁去做新的根节点),如何选?


Eg:


  • 🟠假如按数组的下标顺下去,让下一个数作为新的根结点(即指上图中的5)的话,那树原来的结构就被打乱了,需要重新建堆,才能再次选出最小的

  • 建堆的时间复杂度为,那整体排序下来时间复杂度便为

  • 🟡最终发现如果按照这种方式进行排序的话,相当于建堆的作用就是选数,还不如直接遍历数组选数进行排序,那次是堆排序就没有意义了


⭐但事实真的是这样吗?并不!


➡️方法:


  • 1️⃣建堆


假如我们调转一下思路,排升序不用小堆,而是:


  • 升序:建大堆

  • 降序:建小堆


Eg:


  • 2️⃣利用堆删除的思想进行排序


  1. 堆顶的数据与堆尾数据进行交换,这样就达到排好最大值的效果



  1. 将排好的数字不再纳入建堆中【即建堆的目的就是选出最大值,所以已经选出来的,就无需要再参加】

  2. 并将交换后产生新的树进行重新建堆【因为此时只有根节点发生变化,而左、右子树的关系并没有改变,所以可以利用向下调整算法进行建堆】


4. 重复上述步骤即可,直至里只剩下一个元素,才截止


动图示例: 完整过程



✊综上:堆排序的代码实现【时间复杂度:


void ADjustDown(int * a, int n, int parent){    //大堆    int child = parent * 2 + 1;
while (child < n) //当 孩子的下标 超出 数组的范围,则说明不存在 { //1.选出左右孩子中,较小的一个 //child -- 左孩子下标;child+1 -- 右孩子下标 if (child + 1 < n && a[child + 1] > a[child]) { //想象的时候:默认左孩子是比右孩子小 //如果大的话,child就走到右孩子下标处 child++; }
//2.交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { //满足的情况 break; } }}
复制代码


void HeadSort(int* a,int n){    //建堆 --- 时间复杂度:O(N)    //大堆    for (int i = (n - 1 - 1) / 2; i >= 0; i--)    {        ADjustDown(a, n, i);    }        int end = n - 1;
while (end > 0) //end = 0的时候就截止:即 长度为0就截止 { Swap(&a[0], &a[end]);
//选出次大值 ADjustDown(a, end, 0); end--; }}
复制代码

🥐Ⅱ.Top-K 问题

💡Top - K:


  • 意思就是:求数据中前K个最大的元素或者最小的元素

  • 比如:在高考出成绩时,需要对全省考生的成绩进行排序并取出前 50 名考生的成绩进行封锁,此时就涉及Top-K问题了


👉我们便以题目去理解它吧~

🏷️最小的 K 个数【难度:简单】

:mag:题目传送门:



输入整数数组 arr ,找出其中最小的 k个数


例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4


  • 示例 1:


输入:arr = [3,2,1], k = 2输出:[1,2] 或者 [2,1]
复制代码


  • 示例 2:


输入:arr = [0,1,2,1], k = 1输出:[0]
复制代码


💡解题关键: 找出前K个最小的元素

➡️ 思路一:堆排序

  • 利用我们刚刚所学的堆排序,对数组进行排序,然后取出前K个即可


特别注意:


  • 我们需要自己先实现一个堆排序,再进行使用

  • 在用完后,记得销毁,否则会造成内存泄露


👉实现:


int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    int* returnArray = (int*)malloc(k * sizeof(int)) ;
HeadSort(arr,arrSize);
for(int i = 0; i < k; i++) { returnArray[i] = arr[i]; }
*returnSize = k;
return returnArray;}
复制代码


💫但目前堆排序的效率为:,是否还能优化呢?

⭐答案是可以的

➡️ 思路二: 建堆

  • 根据题意,我们只需要取出最小的前K个数即可,那我们便可以不对数组进行排序,而是利用小堆的特性:每个父亲结点的值总是孩子结点的值

  • 只需要对这个数组进行建堆(建成小堆)即可,然后每次都取出根节点(最小值),一共取K次,便是最小的前K个元素


特别注意:


  • 我们需要自己先实现一个,再进行使用


👉实现:


1️⃣实现


<font color="green"><code class="language-c">typedef int HPDataType;typedef struct Heap{    HPDataType* a;    int size;    int capacity;}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);
void HeapDestroy(HP* php);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
void Swap(HPDataType* p1, HPDataType* p2){ HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp;}
void HeapInit(HP* php, HPDataType* a, int n){ assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*n); if (php->a == NULL) { printf("malloc fail\n");
exit(-1); } //1.拷贝 memcpy(php->a, a, sizeof(HPDataType)*n); php->size = n; php->capacity = n;
//2.建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDwon(php->a, php->size, i); }}

void HeapDestroy(HP* php){ assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0;}
void AdjustUp(HPDataType* a, int child){ int parent = (child - 1) / 2; //while (parent >= 0) while (child > 0) { //if (a[child] < a[parent]) if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } }}
//建小堆void AdjustDwon(HPDataType* a, int size, int parent){ int child = parent * 2 + 1; while (child < size) { // 选出左右孩子中小/大的那个 if (child+1 < size && a[child+1] < a[child]) { ++child; }
// 孩子跟父亲比较 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
void HeapPop(HP* php){ assert(php); assert(php->size > 0);
Swap(&(php->a[0]), &(php->a[php->size - 1])); php->size--;
AdjustDwon(php->a, php->size, 0);}
HPDataType HeapTop(HP* php){ assert(php); assert(php->size > 0);
return php->a[0];}</code></font>
复制代码


2️⃣实现Top-K


<font color="green"><code class="language-c">int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    HP hp;    HeapInit(&hp,arr,arrSize);
int* retArr = (int*)malloc(sizeof(int)*k); for(int i = 0;i < k; i++) { retArr[i] = HeapTop(&hp); HeapPop(&hp); }
HeapDestroy(&hp); *returnSize = k;
return retArr;}</code></font>
复制代码


💫但目前的效率为:,是否还能优化呢?

⭐答案是可以的

➡️ 思路三: 建前 K 个数的堆

  • 类似于建堆的操作,但不同的是,建堆是对数组内全部元素进行调整

  • 但我们现在只需要针对前K个数进行建堆即可


特别注意:


  • 找前k个最大的元素,则建小堆

  • 找前k个最小的元素,则建大堆


👉步骤:


  • 1️⃣用数据集合中前K个元素来建堆【因为这里需要找前K个最小的元素,所以建大堆

  • 2️⃣剩余的N-K个元素(N为总元素个数)依次与堆顶元素来比较,不满足则替换堆顶元素,再向下调整

  • 3️⃣将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素


【我们现在这里建的是大堆,如果与堆顶元素比较时,外面的某个元素小于堆顶的值,则为不满足】


特别注意:


  • 🔴本质:通过数组剩下的N-K个元素,找到比前K个元素的堆中的堆顶元素小的元素,进行轮换

  • 1️⃣即在剩下的元素中,找到比堆顶还小的元素,不断轮换中元素的最大值

  • 2️⃣因为要找的是最小的K个元素,所以最小的前K个一定比大堆堆顶的数据小,一定可以进堆中

  • 🟡这也是为什么建大堆的原因,保证前K个最小的元素中的最小值进来一定不会在堆顶位置(以防前K个最小的元素中的最大值进不来)

  • 🔵现在即使是前K个最小的元素中的最大值进堆,那前K-1个最小的元素还是依然可以进堆

  • 🟣直至这K个数据的堆不再进入元素,说明此时堆内的K个数据就是前K个最小的元素【堆外面没有比这K个元素更小的数了】


亮点:


  • 1️⃣在面对大量数据且无论多大的时候,需要解决Top-K问题时,这个方法依然受用,因为我们始终是在维护一个K个数的堆【只需要遍历剩下的元素进行比较、进堆、向下调整而已】

  • 2️⃣此方法的时间复杂度始终为:

  • 这是因为需要遍历N-K 个元素与堆顶元素进行比较

  • 若不满足进堆后,需要向下调整(有K个元素进行向下调整)【

  • 3️⃣此方法的空间复杂度为:


动图示例:




👉实现:


1️⃣实现建堆


<font color="green"><font color="green"><code class="language-c">void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDwon(HPDataType* a, int size, int parent);
void Swap(HPDataType* p1, HPDataType* p2){ HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp;}
//建大堆void AdjustDwon(HPDataType* a, int size, int parent){ int child = parent * 2 + 1; while (child < size) { // 选出左右孩子中小/大的那个 if (child+1 < size && a[child+1] > a[child]) { ++child; }
// 孩子跟父亲比较 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }</code></font></font>
复制代码


2️⃣实现Top-K


<font color="green"><font color="green"><code class="language-c">int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    if(k == 0)    {        *returnSize = 0;        return NULL;    }
int* arrRet = (int*)malloc(sizeof(int)*k);
//找前K个最小 -- 前k个数建大堆 for(int i = 0; i < k; i++) { arrRet[i] = arr[i]; }
for(int j = (k-1-1) / 2; j >= 0; j--) { AdjustDwon(arrRet,k,j); }
//剩下的N-K个数,比堆顶小的,就替换堆顶数据,进堆调整 for(int l=k;l<arrSize; l++) { if(arr[l] < arrRet[0]) { arrRet[0] = arr[l]; AdjustDwon(arrRet, k, 0); } } *returnSize = k; return arrRet;}</code></font></font>
复制代码

🥯Ⅲ.总结

✨综上:就是堆的应用啦~


➡️相信大家对堆的应用有不一样的看法了吧🧡



🫓总结

综上,我们基本了解了数据结构中的“堆的应用”的知识啦~~


恭喜你的内功又双叒叕得到了提高!!!


感谢你们的阅读


后续还会继续更新,欢迎持续关注哟~


发布于: 刚刚阅读数: 3
用户头像

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

评论

发布
暂无评论
【数据结构与算法】“堆”还能这样用_堆的应用_面试_Dream-Y.ocean_InfoQ写作社区