【数据结构】堆排序和TOPK问题

这篇具有很好参考价值的文章主要介绍了【数据结构】堆排序和TOPK问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏:数据结构
🔊本专栏主要更新的是数据结构部分知识点
💪种一棵树最好是十年前其次是现在

目录

0.利用堆的实现进行排序

1.堆排序

1.1 建堆

​编辑

 1.1.1 向上建堆

1.1.2 向下建堆

1.2 时间复杂度分析

1.3 堆排序

2.TopK问题

2.1 实现方法

2.2 实现过程


0.利用堆的实现进行排序

文章链接:【数据结构】堆的实现

在上篇博客里面,我们详细给出了堆的由来及其实现,其实由于堆这个结构的性质,也是可以直接对一个乱序数组实现排序的。不妨假设排升序并且有一个小根堆,实现过程如下:

  1. 首先,把数组里面的每个数都插入(HeapPush)到堆里。(注意HeapPush里面包含向上调整,所以每次插入之后都会保持堆这个结构)
  2. 其次,小根堆的堆顶是最小的,我们只需每次取出堆顶(HeapTop)元素到数组里面,从堆中取完之后,记得删除该元素(HeapPop)。由于HeapPop里面就有向下调整,每次删完之后都会保持堆的结构,也就是说堆顶元素永远都是最小的。接着一直重复上述操作,直至堆为空(HeapEmpty).
void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
	//把数组元素插入到堆里
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	int j = 0;
	//依次遍历,取堆顶元素到数组,++下标,pop堆顶,依次循环
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);//记得销毁
}

int main()
{
	int a[] = { 3,4,1,9,6,7,5,8 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

很显然,每次要进行上述方法排序时都要手搓堆的实现代码,很繁琐!!!

1.堆排序

堆排序就是利用堆的思想来排序,总共分为两步:
1.建堆
2.利用堆删除思想来进行排序

1.1 建堆

关于建堆,有两种方法:

1.使用向上建堆,插入数据的思想建堆
2.使用向下调整建堆

【数据结构】堆排序和TOPK问题

 1.1.1 向上建堆

图解过程:

【数据结构】堆排序和TOPK问题

代码如下:

#include <stdio.h>
#include <assert.h>

void AdjustUp(int* a, int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])//小堆
        {
            int tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

//升序
void HeapSort(int* a, int n)
{
    //建堆
    for (int i = 1; i < n; i++)//i从1开始遍历,因为第一个数据在堆里不需要调整,后续再插入时调整
    {
        AdjustUp(a, i);
    }
}


int main()
{
    int a[] = { 3,4,1,9,6,7,5,8 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

运行结果:

【数据结构】堆排序和TOPK问题

1.1.2 向下建堆

首先不能直接进行向下调整,因为向下调整的前提是 必须保证根结点的左右子树均为小堆,但是这里的数组是乱序的,因此不能直接使用。但是我们可以 从倒数第一个非叶结点开始向下调整,从下往上调。这又出现了一个问题,那就是倒数第一个非叶结点在哪呢,通过画逻辑图不难看出,其实 最后一个结点的父亲就是倒数第一个非叶结点。当我们找到这个非叶结点时,把它和它的孩子看作一个整体,进行向下调整。调整之后,再将次父结点向前挪动,再次进行向下调整,依次循环下去。

图解过程:

【数据结构】堆排序和TOPK问题

#include <stdio.h>
#include <assert.h>

void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

void AdjustUp(int* a, int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])//小堆
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void AdjustDown(int* a, int n, int parent)
{
    int child = 2 * parent + 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 = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }

}


//升序
void HeapSort(int* a, int n)
{
    建堆
    //for (int i = 1; i < n; i++)//i从1开始遍历,因为第一个数据在堆里不需要调整,后续再插入时调整
    //{
    //    AdjustUp(a, i);
    //}
    
    //建堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
}

int main()
{
    int a[] = { 3,4,1,9,6,7,5,8 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

运行结果:

【数据结构】堆排序和TOPK问题

 满足小堆性质。

1.2 时间复杂度分析

1.1中的向上建堆和向下建堆哪个时间复杂度更小呢?

【数据结构】堆排序和TOPK问题

【数据结构】堆排序和TOPK问题

 综上所得,向下建堆时间复杂度更低。即使我们不用公式去推,我们也可以直观感受到二叉树越往下的结点就越多,下面结点越多向下建堆的次数就越少,而向上建堆相反,下面越多反而向上建堆的次数就越多。相比之下,向上建堆的复杂度明显高于向下建堆。

1.3 堆排序

在进行堆排序之前要思考一个问题——升序降序分别应该建什么堆?

解:假设升序建小堆,有了上述时间复杂度的分析,我们采用复杂度较低的向下建堆,并且建好堆之后,堆顶元素必然是最小的一个。如果继续使用小堆的话,从第二个数开始往后当作堆,此时堆这个结构全乱了。反之,如果采用大堆的话,就会方便很多。因此升序要建大堆

下面进入堆排序正文部分:

1.先建好大堆: 

【数据结构】堆排序和TOPK问题

2.核心操作:我们把第一个数和最后一个数互换位置,并且最后一个数直接丢掉,即数组下标减减。此时左右子树仍是大堆,就可以再次进行向下调整。

图解过程(注:因为是最后一个元素不看做堆里的部分,因此是倒序确定)【数据结构】堆排序和TOPK问题

 代码如下:
 

#include <stdio.h>
#include <assert.h>

void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}


void AdjustDown(int* a, int n, int parent)
{
    int child = 2 * parent + 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 = 2 * parent + 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);
        end--;
    }
}

int main()
{
    int a[] = { 3,4,1,9,6,7,5,8 };
    HeapSort(a, sizeof(a) / sizeof(int));
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

输出结果:

【数据结构】堆排序和TOPK问题

2.TopK问题

TopK问题,顾名思义就是N个数里面找出最大/最小的前k个。通常适用于数据比较大的情况。
这里我们不妨取在10000个数里面找出最大的前10个。

2.1 实现方法

对于TopK问题,通常会有以下几种方法:
1.排序:先排降序(快排),前10个就是最大的。
2.将N个数依次插入大堆,再pop个k次,每次取出栈顶元素。

相较于法一,法二似乎更优,然而这也引发了一些问题:如果N非常大,以至于远远大于k。此时法一法二就不能在用了,因为此时会导致内存不足。因此就有了法三的由来:

3. 用前k个数建立一个k个数的小堆,然后让剩下的N-K个依次遍历,如果比堆顶的数据大,就替换它进堆(向下调整),最后堆里面剩下的就是最大的前k个

2.2 实现过程

test.c文章来源地址https://www.toymoban.com/news/detail-429252.html

// 向下调整
void AdjustDown(int* a, int n, int parent)
{
    int child = 2 * parent + 1;
    while (child < n)
    {
        //选出左右孩子中小的那个
        if (a[child + 1] < a[child])
        {
            ++child;
        }
        //如果小的孩子小于父亲,则交换,并继续向下调整
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

void PrintTopK(int* a, int n, int k)
{
    // 1. 建堆--用a中前k个元素建堆
    int* minHeap = (int*)malloc(sizeof(int) * k);
    assert(minHeap);
    for (int i = 0; i < k; i++)
    {
        minHeap[i] = a[i];
    }
    // 2. 建小堆
    for (int j = (k - 1 - 1) / 2; j >= 0; j--)
    {
        //从倒数第一个非叶结点开始
        AdjustDown(a, k, j);
    }
    // 3. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
    for (int i = k; i < n; i++)
    {
        if (a[i] > minHeap[0])
        {
            minHeap[0] = a[i];//如果比堆顶大就替换他
            AdjustDown(minHeap, k, 0);// 向下调整确保为堆
        }
    }
    for (int j = 0; j < k; j++)
    {
        printf("%d ", minHeap[j]);//打印
    }
    printf("\n");
    free(minHeap);//销毁
}

void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;//生成一个随机数,使其数值都小于1000000
    }
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2335] = 1000000 + 6;
    a[9999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
    PrintTopK(a, n, 10);
}

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

到了这里,关于【数据结构】堆排序和TOPK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(42)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(38)
  • 【数据结构之二叉树简介·顺序存储·应用:堆·堆排序·TOPK问题】

    ​ 🕺作者: 迷茫的启明星 😘欢迎关注:👍点赞🙌收藏✍️留言 🎃相关文章 【数据结构从0到1之树的初识】 【数据结构】带你学会二叉树的链式存储的前中后序遍历,遍历推导及利用队列实现二叉树的层次遍历。 🏇家人们,码字不易,你的👍点赞🙌收藏❤️关注对我

    2024年02月01日
    浏览(35)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(40)
  • 【数据结构】---TopK问题

    本文提供用建堆来解决TopK问题的一个思路 N个数中找出最大的或者最小的前k个 假设现从N个数中找最小的前k个 ①堆排序, 时间复杂度O(N*logN),这N个数排一下序,前k个数就是需要的 ②建堆N个数的小堆 ,HeapPop k-1 次,就选出来了,因为小堆最小的在堆顶,选出一次后,再删除

    2024年02月12日
    浏览(46)
  • 【数据结构】——解决topk问题

    前言:我们前面已经学习了小堆并且也实现了小堆,那么我们如果要从多个数据里选出最大的几个数据该怎么办呢,这节课我们就来解决这个问题。我们就用建小堆的方法来解决。 首先我们来看到这个方法的时间复杂度,我们先取前k个数据建立一个小堆,后面插入的数据依

    2024年02月04日
    浏览(40)
  • 【数据结构】【堆】 堆排,TOPK问题

    堆排序,就是先将数据构建成堆,根据需要构建大堆或者小堆。 如果要排降序,就构建小堆。 如果要排升序,就构建大堆。 我们 以降序为例 : 在构建好小堆后,堆顶的数据就是最小的。 我们将堆顶数据与最后一个数据进行交换,然后把堆的最后一个位置排除在外(即它不

    2024年02月07日
    浏览(36)
  • 【数据结构】堆的应用-----TopK问题

    目录 一、前言 二、Top-k问题   💦解法一:暴力排序 💦解法二:建立N个数的堆 💦解法三:建立K个数的堆(最优解) 三、完整代码和视图  四、共勉 在之前的文章中,已经详细的讲解了二叉树、堆、堆排序。那么关于堆还有一个比较有意思的题,就是TopK问题。 如果对堆

    2024年02月07日
    浏览(46)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(58)
  • 数据结构之树(Topk问题, 链式二叉树)

    取N个数中最大(小)的前k个值,N远大于k 这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆 时间复杂度O(k) 之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整 时间复杂度(N-k)*log(N) 总共的时间复杂度为O(N*log(N)) 用数组

    2024年03月15日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包