AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构】堆，堆的实现，堆排序，TOP-K问题

2024-07-19 33
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构——堆，堆的实现，堆排序，TOP-K问题

​

1. 堆的概念及结构

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

堆分为最小堆（Min Heap）和 最大堆（Max Heap）。对于最小堆，父结点的值小于等于它的子结点的值。对于最大堆，父结点的值大于等于它的子结点的值；
image.png
image.png

堆的性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值。

2. 堆总是一棵完全二叉树。

3. 小堆的根是整棵树的最小值，大堆的根是整棵树的最大值。

问题：

  1. 小堆的底层数组是否升序？
    image.png

  2. 大堆的底层数组是否降序？
    image.png

2. 堆的实现

我们这里以小根堆为例（大根堆可以在小根堆的基础上稍作修改），下面是要实现堆的接口函数：

//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestroy(HP* php);
//打印堆
void HeapPrint(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆向上调整算法
void AdjustUp(HPDataType* a, int child);
//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//取堆顶的数据
HPDataType HeapTop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HeapEmpty(HP* php);

堆的定义：

typedef int HPDataType;
typedef struct Heap
{
   
   
    HPDataType* a;
    int size;
    int capacity;
}HP;

一些简单的接口函数，和我们之前实现的顺序表，链表，栈等数据结构类似。我们在这里就不详细介绍了，这里我们主要介绍堆向上调整算法和堆向下调整算法。这两个函数分别会在堆的插入和堆的删除中调用。

2.1 初始化堆

//初始化堆
void HeapInit(HP* php)
{
   
   
    assert(php);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}

2.2 销毁堆

//销毁堆
void HeapDestroy(HP* php)
{
   
   
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

2.3 打印堆

//打印堆
void HeapPrint(HP* php)
{
   
   
    assert(php);
    for (int i = 0; i < php->size; i++)
    {
   
   
        printf("%d ", php->a[i]);
    }
    printf("\n");
}

2.4 交换函数

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
   
   
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

2.5 堆的向上调整

向上调整前提：前面的数据是堆
image.png

//堆向上调整算法
void AdjustUp(HPDataType* a, int child)
{
   
   
    int parent = (child - 1) / 2;
    while (child > 0)
    {
   
   
        if (a[child] < a[parent])
        {
   
   
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else 
        {
   
   
            break;
        }    
    }
}

2.6 堆的向下调整

向下调整前提：左右子树都是小堆或者都是大堆
image.png

//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
   
   
    int child = parent * 2 + 1;
    while (child < n)
    {
   
   
        if (child + 1 < n && a[child + 1] < a[child]) //找出小的那个孩子
        {
   
   
            ++child;
        }
        if (a[child] < a[parent])
        {
   
   
            Swap(&a[child], &a[parent]);
            parent = child; 
            child = parent * 2 + 1;
        }
        else
        {
   
   
            break;
        }
    }
}

2.7 堆的插入

向堆中插入一个元素，就是这个元素插入到堆的尾部，因为堆的实际存储结构是一个数组，我们可以将元素放到数组末尾。

但是如果仅仅是将元素插入到数组末尾的话，会破坏堆的结构，我们还需要调用一个向上调整函数，保持堆的结构。

注意：在插入之前，我们需要判断堆的容量是否足够，如果堆的容量已满，需要扩容，扩容时我们在原来的基础上扩2倍。

如下图：
image.png

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

//堆的插入
void HeapPush(HP* php, HPDataType x)
{
   
   
    assert(php);
    if (php->size == php->capacity)
    {
   
   
        int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL)
        {
   
   
            perror("realloc failed");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

2.8 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
image.png

//堆的删除
void HeapPop(HP* php)
{
   
   
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    --php->size;
    AdjustDown(php->a, php->size, 0);
}

2.9 取堆顶的数据

//取堆顶的数据
HPDataType HeapTop(HP* php)
{
   
   
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

2.10 堆的数据个数

//堆的数据个数
int HeapSize(HP* php) 
{
   
   
    assert(php);
    return php->size;
}

2.11 堆的判空

//堆的判空
bool HeapEmpty(HP* php)
{
   
   
    assert(php);
    return php->size == 0;
}

3. 堆的实现的完整代码

3.1 Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
   
   
    HPDataType* a;
    int size;
    int capacity;
}HP;


//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestroy(HP* php);
//打印堆
void HeapPrint(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆向上调整算法
void AdjustUp(HPDataType* a, int child);
//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//取堆顶的数据
HPDataType HeapTop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HeapEmpty(HP* php);

3.2 Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//初始化堆
void HeapInit(HP* php)
{
   
   
    assert(php);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}

//销毁堆
void HeapDestroy(HP* php)
{
   
   
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

//打印堆
void HeapPrint(HP* php)
{
   
   
    assert(php);
    for (int i = 0; i < php->size; i++)
    {
   
   
        printf("%d ", php->a[i]);
    }
    printf("\n");
}

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
   
   
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

//堆向上调整算法
void AdjustUp(HPDataType* a, int child)
{
   
   
    int parent = (child - 1) / 2;
    while (child > 0)
    {
   
   
        if (a[child] < a[parent])
        {
   
   
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else 
        {
   
   
            break;
        }    
    }
}

//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
   
   
    int child = parent * 2 + 1;
    while (child < n)
    {
   
   
        if (child + 1 < n && 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 HeapPush(HP* php, HPDataType x)
{
   
   
    assert(php);
    if (php->size == php->capacity)
    {
   
   
        int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL)
        {
   
   
            perror("realloc failed");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

//堆的删除
void HeapPop(HP* php)
{
   
   
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    --php->size;
    AdjustDown(php->a, php->size, 0);
}

//取堆顶的数据
HPDataType HeapTop(HP* php)
{
   
   
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

//堆的数据个数
int HeapSize(HP* php) 
{
   
   
    assert(php);
    return php->size;
}

//堆的判空
bool HeapEmpty(HP* php)
{
   
   
    assert(php);
    return php->size == 0;
}

3.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

int main()
{
   
   
    int a[] = {
   
    2,3,5,7,4,6,8};
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
   
   
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    int sz = HeapSize(&hp);
    printf("堆中元素个数为%d个\n", sz);

    while (!HeapEmpty(&hp))
    {
   
   
        printf("%d ", HeapTop(&hp));
        HeapPop(&hp);
    }
    HeapDestroy(&hp);
    return 0;
}

4. 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

4.1 向上调整建堆

image.png

因此向上调整建堆的时间复杂度是O(N*logN)

4.2 向下调整建堆

image.png

因此，向下调整建堆的时间复杂度为O(N)

因为向下调整建堆的时间复杂度是O(N)，小于向上调整建堆的时间复杂度O(N*logN)，所以一般情况下，我们都采用向下调整建堆。

5. 堆的应用

5.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆

升序：建大堆

降序：建小堆

  1. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

这里我们以大堆为例，通过堆排序进行升序
image.png

我们也可以在堆的底层数组中进一步理解堆排序的过程
image.png

因为是大堆，所以我们要稍微修改向下调整部分的代码（我们在上面堆的实现中是以小堆为例）

void Swap(HPDataType* p1, HPDataType* p2)
{
   
   
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
   
   
    int child = parent * 2 + 1;
    while (child < n)
    {
   
   
        if (child + 1 < n && 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 HeapSort(int* a, int n)
{
   
   
    //从倒数第一个非叶子结点开始调
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
   
   
        AdjustDown(a, n, i);  //向下调整建堆
    }
    int end = n - 1;
    while (end > 0)
    {
   
   
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);  //向下调整[0,end]的元素
        --end;
    }
}

int main()
{
   
   
    int a[] = {
   
    20,17,4,16,5,3 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i=0 ; i < sizeof(a) / sizeof(int); i++)
    {
   
   
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

image.png

5.2 TOP-K问题

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

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

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

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

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

实际应用：在1000000个随机数中找出前十个最大的数字 

void PrintTopK(int* a, int n, int k)
{
   
   
    int* KMaxHeap = (int*)malloc(sizeof(int) * k);
    assert(KMaxHeap);
    for (int i = 0; i < k; i++)
    {
   
   
        KMaxHeap[i] = a[i];
    }
    //建小根堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
   
   
        AdjustDown(KMaxHeap, k, i);
    }
    //依次比较a数组中剩余的元素
    for (int i = k; i < n; i++)
    {
   
   
        if (a[i] > KMaxHeap[0])
        {
   
   
            KMaxHeap[0] = a[i];
        }
        AdjustDown(KMaxHeap, k, 0);
    }
    //打印
    for (int i = 0; i < k; i++)
    {
   
   
        printf("%d ", KMaxHeap[i]);
    }
    printf("\n");
}

void TestTopK()
{
   
   
    int n = 1000000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
   
   
        a[i] = rand() % n;
    }
    //手动设定10个最大的数
    a[5] = n + 1;
    a[1231] = n + 2;
    a[531] = n + 3;
    a[5121] = n + 4;
    a[115] = n + 5;
    a[2335] = n + 6;
    a[9999] = n + 7;
    a[76] = n + 8;
    a[423] = n + 9;
    a[3144] = n + 10;
    PrintTopK(a, n, 10);
}

int main()
{
   
   
    TestTopK();
    return 0;
}

image.png

6. 总结

到这里，我们就用学习完了数据结构中堆的相关知识点。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！

​

文章标签：
算法
存储
关键词：
数据结构堆
数据结构堆排序
数据结构堆堆排序top-k
数据结构堆top-k
数据结构堆堆排序
是基德吖
目录
相关文章
Star时光
|
12天前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
Star时光
82 0
qq2108462953
|
24天前
|
算法 机器人
【数据结构】什么是堆
【数据结构】什么是堆
qq2108462953
31 0
aliyun6365824167
|
26天前
|
搜索推荐 算法
【初阶数据结构篇】插入、希尔、选择、堆排序介绍（上篇）
堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。
aliyun6365824167
10 0
aliyun6365824167
|
26天前
|
算法
【初阶数据结构篇】堆的应用（堆排序与Top-K问题）
即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。
aliyun6365824167
23 0
aliyun6365824167
|
26天前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）
注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++
aliyun6365824167
13 0
小徐在进步
|
2天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
19 8
小徐在进步
|
4天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
20 3
2的n次方_
|
6天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
11 0
【数据结构】栈和队列的深度探索，从实现到应用详解
服务端技术栈
|
29天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
37 1
栈的几个经典应用，真的绝了
可能只会写BUG
|
10天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
21 2