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

作者：Dream-Y.ocean

2022 年 9 月 27 日
广东
本文字数：5102 字
阅读完需：约 17 分钟

前情提要

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

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

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

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

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

💡本章重点

堆排序
Top-K 问题

🍞堆的应用

🥐Ⅰ.堆排序

💡堆排序：

本质为选择排序的一种
堆排序便是利用堆这种数据结构的思想进行排序

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

🔥 思想：

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

❓思考： 如何利用堆进行排序

假如排升序，我们利用小堆进行排序的话：
我们建好一个小堆后，因为小堆的特性为最小的数在根节点处（最上面），我们便排好升序中的第一个数字
此时我们再继续排剩下的数字，便需要在建堆的时候剔除已经排好的数字，继而将剩下的重新的建堆，选最小的数字
重复上述步骤即可

❗特别注意：

如果按照上述方法进行排序的话，有两个问题：
🔴第一次建好堆后，在选出最小的数字放到第一个位置紧接着要选出次小的（即进行第二次建堆选数，谁去做新的根节点），如何选？

Eg：

🟠假如按数组的下标顺下去，让下一个数作为新的根结点（即指上图中的5）的话，那树原来的结构就被打乱了，需要重新建堆，才能再次选出最小的
建堆的时间复杂度为 $O (N)$ ，那整体排序下来时间复杂度便为 $O (N^{2})$
🟡最终发现如果按照这种方式进行排序的话，相当于建堆的作用就是选数，还不如直接遍历数组选数进行排序，那次是堆排序就没有意义了

⭐但事实真的是这样吗？并不！

➡️方法：

1️⃣建堆

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

升序：建大堆
降序：建小堆

Eg：

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

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

将排好的数字不再纳入建堆中【即建堆的目的就是选出最大值，所以已经选出来的，就无需要再参加】
并将交换后产生新的树进行重新建堆【因为此时只有根节点发生变化，而左、右子树的关系并没有改变，所以可以利用向下调整算法进行建堆】

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

✊动图示例： 完整过程

✊综上：堆排序的代码实现【时间复杂度： $O (N * l o g N)$ 】

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

复制代码

💫但目前堆排序的效率为： $O (N * l o g N)$ ，是否还能优化呢？
⭐答案是可以的

➡️ 思路二：建堆

根据题意，我们只需要取出最小的前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>

复制代码

💫但目前堆的效率为： $O (N + k * l o g N)$ ，是否还能优化呢？
⭐答案是可以的

➡️ 思路三：建前 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️⃣此方法的时间复杂度始终为： $O ((N - K) * l o g K)$
这是因为需要遍历N-K 个元素与堆顶元素进行比较
若不满足进堆后，需要向下调整（有K个元素进行向下调整）【 $O (l o g k)$ 】
3️⃣此方法的空间复杂度为： $O (K)$

✊动图示例：

👉实现：

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

原文链接:【http://xie.infoq.cn/article/c703a15829b97a1a8ad371536】。未经作者许可，禁止转载。

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

发布

暂无评论

创作场景

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

💡本章重点

🍞堆的应用

🥐Ⅰ.堆排序

🥐Ⅱ.Top-K 问题

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

➡️ 思路一：堆排序

➡️ 思路二： 建堆

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

🥯Ⅲ.总结

🫓总结

Dream-Y.ocean

评论

➡️ 思路二：建堆

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