堆排序

堆排序的前提

堆排序:是指利用堆这种数据结构所设计的一种排序算法。堆排序通过建大堆或者小堆来进行排序的算法。

举个例子:给定我们一个数组{2, 3,4, 2,4,7},我们可把这个数组在逻辑上看成是一种堆的结构,然后进行建堆,建大堆(或建小堆)我们就可以在堆顶选出一个最大(最小)的数,通过不断的选数,我们就可以把顺序弄出来了。

如何建堆?在上一篇博客中我已经跟大家说过了,就是这样的:

堆的构建有两种方法:

第一种:从第二个节点往后开始向上调整

第二种:从最后一个非叶子节点开始向下调整

第一种:从第二个叶子节点开始向上调整,把前面两个节点构成的堆建成大堆(小堆),如何依次调整第三个节点,第四个节点……直到调整最后一个,与堆的插入有些相似,只不过我们原来是有一组数,用一个动图给大家演示一下:

代码实现如下:

int i = 0;
//建小堆 排降序 建大堆 排升序
for (i = 1; i < n; i++)
{
//建大堆 向下调整
AdjustUp(i);
}

第二种:从最后一个非叶子节点开始向下调整,从下往上,先把下面的子树建成大堆(小堆),最后就是堆顶向下调整了,看一下动图演示:

代码实现如下:

//找到最后一个父亲节点
int parent = (n - 2) / 2;
int i = 0;
//建小堆 排降序 建大堆 排升序
for (i = parent; i >= 0; i--)
{
//建大堆 向下调整
AdjustDown(n, i);
}

堆排序的思想

如果把待排序序列分为未排序区间和有序区间,堆排序大的思想是每次选一个数放到有序区间,没经历一个循环有序区间就会加一,无序区间减一,循环结束序列也就有序了,像这样:

可以发现堆排序的思路和选择排序很像,没错,思路确实一样,只不过选择排序每次要遍历无序区间去找当前无序区间的最大值(升序找最大值,降序找最小值),而堆排序呢是吧无序区间看做一个堆,堆顶自然是这个堆的最值了,每次循环只需要将堆顶元素取出来和无序区间最后一个数交换以达到有序区间加一的目的,然后在对这个堆(注意此时堆的size减一)向下调整,这样做之后下次循环继续取堆顶元素和无序区间最后一个元素交换然后继续循环,直到无序区间就剩一个元素,此时整个序列就有序了。

对于堆排序在实现的时候要知道:

  1. 待排序序列需要升序排列那么要建大堆
  2. 待排序序列需要降序排列那么要建小堆

为什么要有上面的两条规定呢?要升序排列就不能建小堆,要降序排列就不能建大堆吗?

答案是可以,但是不推荐,请看下图:

相反如果要通过建小堆完成让数组升序排列的话,因为小堆堆顶元素是最小值,而堆顶这个位置也是排序之后最小值的位置就是说堆顶元素不用在移动了,那么我们的堆要从后面一位重新建立,在建立一个小堆,找出最小值,再往后面一位找出最小值直到整个数组成升序排列,乍一看好像没有问题,但是和建大堆不同的是建小堆每次都要从下一位重新建堆才能选出最值,这个操作的复杂度为O(nlogn),要比建大堆每次只用将堆顶元素向下调整的时间复杂度为O(logn)慢很多,所以虽然可以升序建小堆但是因为相对没有建大堆速度快所以我们选择建大堆。

对应的降序建小堆也是同理。

总结

  1. 待排序序列需要升序排列那么要建大堆
  2. 待排序序列需要降序排列那么要建小堆

堆排序的基本步骤以及代码

步骤一 :构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。

a.假定给定的无序序列结构如下,将通过方法二从最后一个非叶子节点开始向下调整,将该堆编程一个大堆

b.我们对整个无序序列进行调整,将其建立成大堆的形式,此时我们从最后一个非叶子结点开始进行调整,找到第一个非叶子结点8,比较它的左右子节点,找出左右子节点的最大值,与父结点进行比较,如果比父节点大就交换,得到调整后的结构

c.找到第二个非叶子结点16,由于它的左右子结点25和18中25的元素大,所以将16和25进行交换,得到如下序列,此时向下调整还没有结束,以16为目标结点,比较其与左右子节点的大小关系,发现已经成堆,结束调整(切记向下调整还没有完毕,需要以交换的结点为目标继续查看是否需要继续向下调整)

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素25和末尾元素8进行交换,此时25为有序序列,前面为无序

b.重新调整结构,使其继续满足堆定义,以16为第一个非叶子结点进行向下调整,紧接着以8为第二个非叶子结点进行调整,将18和8互换,此时18是左右孩子最大的值,不需要再向下调整

c.将堆顶元素18和末尾元素15进行交换,此时18,25为有序序列,前面为无序

d.重新调整结构,使其继续满足堆定义,以15为第一个非叶子结点进行向下调整,将16和15进行交换

e.将堆顶元素16和末尾元素8进行交换,此时16,18,25为有序序列,前面为无序

d.重新调整结构,使其继续满足堆定义,以8为第一个非叶子结点进行调整,将15和8互换,调整完毕之后,交换15和8的值,得到最终的有序序列,堆排序过程结束

再简单总结下堆排序的基本思路:

  a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

  b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

  c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

堆排序的代码实现

template <class DateType>
//小堆的实现
class MinHeap
{
public:
private:
int size;
int capacity;
DateType* data;
};

这里的HeapSort堆排序函数为了显示的直观,就不放在类内定义,若放在类内定义,这个DateType* a其实是不用写的,用this指针直接指向就可以了,但是这里为了更直观的展示,就不去掉这个指针了,希望小伙伴们不要混淆,上一篇博客中定义在类内的成员函数都没有传入DateType* a,但是其他博客中使用结构体定义的,需要传入这个指针,是有区别的,希望小伙伴们不要混淆。

void HeapSort(DateType* data, int n)
{
//找到最后一个父亲节点
int parent = (n - 1 - 1) / 2;
int i = 0;
//建小堆 排降序 建大堆 排升序
for (i = parent; i >= 0; i--)
{
//建大堆 向下调整
AdjustDown(data, n, i);
} i = n - 1;
while (i >= 0)
{
Swap(&data[0], &data[i]);
AdjustDown(data, i, 0);
i--;
}
}

堆排序时间复杂度分析

这里时间复杂度分析分为两部分——建堆n次向下调整

建堆:时间复杂度是O(n)

n次向下调整:向下调整一次是O(logn),n次就是O(n*logn)

n*logn+n≈n*logn

综上,堆排序时间复杂的是O(n*logn)

TOPK问题

TOPK问题的概念

TOPK问题:找出N个数里面最大/最小的前K个问题。

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

TOPK问题实现的原理

原理:TOPK问题采用堆来实现,用一个大小为K的小堆,然后往堆顶插入数据,如果当前的数比堆顶的数大就把堆顶的数换下来并进行向下调整,否则就不做处理。

如果要选取n个数中最大/最小的前k个值,步骤如下:

1.先用前k个数建成k个数的小堆。

2.剩下n-k个数,依次跟堆顶的数据进行比较,如果比堆顶的数据大,就进堆进行向下调整。

3.最后堆里的k个数就是最大的k个数。

举个例子:10选5

TOPK问题代码实现

核心代码

void PrintTopK(int* a, int n, int k)
{
assert(a);
HP hp;
HeapInit(&hp);
// 1. 建堆--用a中前k个元素建堆
for (int i = 0; i < k; ++i)
{
HeapPush(&hp, a[i]);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
for (int i = k; i < n; i++)
{
if (a[i] > hp.a[0])
{
hp.a[0] = a[i];
AdjustDown(hp.a, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", hp.a[i]);
}
}

完整代码以及测试

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int capacity;
int size;
}HP;
void Swap(int* p1, int* p2)
{
int tmp;
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
} void AdjustUp(HPDataType* 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 HeapPush(HP* hp, HPDataType x)
{
assert(hp); if (hp->capacity == hp->size)
{
int newCapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HPDataType* tmp = (HPDataType*)realloc(hp->a, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
} hp->a = tmp;
hp->capacity = newCapacity;
}
hp->size++;
hp->a[hp->size - 1] = x; //向上调整
AdjustUp(hp->a, hp->size - 1);
}
void HeapInit(HP* hp)
{
assert(hp); hp->a = NULL;
hp->capacity = hp->size = 0;
}
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 PrintTopK(int* a, int n, int k)
{
assert(a);
HP hp;
HeapInit(&hp);
// 1. 建堆--用a中前k个元素建堆
for (int i = 0; i < k; ++i)
{
HeapPush(&hp, a[i]);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
for (int i = k; i < n; i++)
{
if (a[i] > hp.a[0])
{
hp.a[0] = a[i];
AdjustDown(hp.a, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", hp.a[i]);
}
}
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;
}
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问题的更多相关文章

  1. R语言实战(一)介绍、数据集与图形初阶

    本文对应<R语言实战>前3章,因为里面大部分内容已经比较熟悉,所以在这里只是起一个索引的作用. 第1章       R语言介绍 获取帮助函数 help(), ? 查看函数帮助 exampl ...

  2. 平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

    平衡树初阶——AVL平衡二叉查找树 一.什么是二叉树 1. 什么是树. 计算机科学里面的树本质是一个树状图.树首先是一个有向无环图,由根节点指向子结点.但是不严格的说,我们也研究无向树.所谓无向树就是 ...

  3. Nodejs初阶之express

    PS: 2014/09/24 更新<Express 4.X 启航指南>,欢迎阅读和评论:)   老规矩,开头部分都是些自娱自乐的随想,想到哪写到哪... 到今天俺已经在俺厂工作俩年零几天了 ...

  4. 重温ASP.NET WebAPI(一)初阶

    重温ASP.NET WebAPI(一)初阶   前言 本文为个人对WebApi的回顾无参考价值.主要简单介绍WEB api和webapi项目的基本结构,并创建简单地webaapi项目实现CRUD操作. ...

  5. 基本数据结构 —— 堆以及堆排序(C++实现)

    目录 什么是堆 堆的存储 堆的操作 结构体定义 判断是否为空 往堆中插入元素 从堆中删除元素 取出堆中最大的元素 堆排序 测试代码 例题 参考资料 什么是堆 堆(英语:heap)是计算机科学中一类特殊 ...

  6. 数据结构与算法---堆排序(Heap sort)

    堆排序基本介绍 1.堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序. 2.堆是具有以下性质的完全二叉树:每个 ...

  7. 算法与数据结构(十四) 堆排序 (Swift 3.0版)

    上篇博客主要讲了冒泡排序.插入排序.希尔排序以及选择排序.本篇博客就来讲一下堆排序(Heap Sort).看到堆排序这个名字我们就应该知道这种排序方式的特点,就是利用堆来讲我们的序列进行排序.&quo ...

  8. 《R语言实战》读书笔记--第三章 图形初阶(一)

    3.1使用图形 可以使用pdf等函数将图形直接保存在文件中.在运用attach和detach函数的使用中经常出现错误,比如命名重复的问题,所以,应该尽量避免使用这两个函数. plot是一般的画图函数, ...

  9. UE4开发神秘海域类游戏原型 初阶(二):动画资源的整合

    前一篇已经确定神海类游戏原型的目标,首先要做的就是3C's(Character, Controls, Camera)的开发.   UE4的3C's的程序部分开发主要也就是基于他的GamePlay Fr ...

  10. R语言—图像初阶

    dev.new() 创建一个新图像之前打开一个新的窗口 win.graph() 同上 pch() 指定绘制点时使用的符号 cex() 指定符号的大小,是一个数值,表示绘图符号相当于默认大小的缩放倍数 ...

随机推荐

  1. Openstack Neutron:三层技术和实现

    目录 - 1.Neutron 三层技术简介 - 2.集中式router - 1.在节点上安装L3 agent - 2.配置外部网络 - 3.通过CLI或者Horizon 来创建路由 - 4.连接租户网 ...

  2. 《Win10——如何设置开机自启动项》

    Win10--如何设置开机自启动项       1. 为需要自启动的程序创建快捷方式. 2. Win+R输入"shell:startup",按下回车键出现一个文件夹. 3. 将快捷 ...

  3. MinIO客户端快速入门指南

    官方文档地址:http://docs.minio.org.cn/docs/master/minio-client-quickstart-guide MinIO Client (mc)为ls,cat,c ...

  4. 第二章:视图层 - 1:URL路由基础

    路由的编写方式是Django2.0和1.11最大的区别所在.Django官方迫于压力和同行的影响,不得不将原来的正则匹配表达式,改为更加简单的path表达式,但依然通过re_path()方法保持对1. ...

  5. [基础]VS Code 基础操作 命令符

    一.五种运行方式 1.点击IIS Express运行 实际上它开的是一个IIS Express服务器,就是说有一个小的代理服务器帮咱们运行,运行后就会启动一个IIS Express小型服务器,启动之后 ...

  6. 【原创】推流录屏软件OBS使用教程--录屏

    之前有录屏需要,写了一篇关于ffmpeg录屏的文章,反响还不错,但是直接用ffmpeg门槛有些高,今天写一篇图形界面的录屏推流工具OBS的使用教程.这次先写OBS的录屏教程 下载安装 点击 OBS官网 ...

  7. 华为 Quidway S3700-28TP-SI-AC Routing Switch 配置时间(ntp)

    设置ntp服务器: [SW03] ntp unicast-server x.x.x.x 记住一定要退出特权模式之后再设置时区 <SW03>clock timezone beijing ad ...

  8. 洛谷P2865 [USACO06NOV]Roadblocks G(次短路)

    一个次短路的问题,可以套用dijkstra求最短路的方法,用dis[0][i]表示最短路:dis[1][i]表示次短路,优先队列中存有最短路和次短路,然后每次找到一条道路对他进行判断,更新最短或次短路 ...

  9. 图解 | 聊聊 MyBatis 缓存

    首发公众号-悟空聊架构:图解 | 聊聊 MyBatis 缓存 你好,我是悟空. 本文主要内容如下: 一.MyBatis 缓存中的常用概念 MyBatis 缓存:它用来优化 SQL 数据库查询的,但是可 ...

  10. 网络安全(一):信息收集之玩转nmap(理论篇)

    更新时间 2022年09月06日16:20:10 完成nmap介绍,目标选择,主机发现部分 2022年10月28日21:19:20 完成最基本的内容,端口扫描,版本和系统探测,安全其他等 打算的更新计 ...