> 文档中心 > 手撕堆的实现(堆排序,Topk问题)——单手吊打数据结构

手撕堆的实现(堆排序,Topk问题)——单手吊打数据结构

目录

    • 传统艺能😎
    • 堆的概念与结构🤔
    • 堆的实现🤔
    • 向上(向下)调整算法🤔
    • 调整算法的时间复杂度对比🤔
    • 建堆时间复杂度🤔
    • 堆排序🤔
    • Topk问题🤔

传统艺能😎

小编是双非本科大一菜鸟不赘述,欢迎大佬指点江山(QQ:1319365055)
此前博客点我!点我!请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库(打灰人 )欢迎访问,点我!

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们,打码路上一路向北,背后烟火,彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区,诚邀各位有志之士的加入!!
社区用户好文均加精(“标兵”文章字数2000+加精,“达人”文章字数1500+加精)
直达: 社区链接点我
在这里插入图片描述

堆的概念与结构🤔

前面讲了二叉树的相关概念,堆就是把他的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中。堆可以用来解决堆排序,topk 问题,以后还会涉及到优先级队列。

堆又分为大堆和小堆,我们把根节点最大的堆叫做大(根)堆,即树中父节点 ≥ 子节点,根节点最小的堆叫做小(根)堆,父节点 ≤ 子节点。

堆的性质:

  1. 堆中的某个节点的值总是不大于或者不小于其父节点的值;
  2. 堆总是一棵完全二叉树;

在这里插入图片描述

堆的实现🤔

一般这种实现我们就直接考虑动态版本:

底层结构我们采用的是顺序表的结构,但注意仅仅只是借鉴他的结构,逻辑上他并不是线性表,不应支持头插尾插头删尾删等操作,是不是有了疑问:他的存储结构不就是一个数组吗,为毛不支持啊?原因很简单,要是支持这些操作不就是一个顺序表了嘛,那我干嘛叫堆是吧。

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

向上(向下)调整算法🤔

这里就有一个细节,格局在此提高,我们所谓入堆出堆,都应该时刻维持他作为堆的结构,想象一下我插入一个数后,结果是他有可能是堆有可能不是堆,因为对于父节点的相对大小我并不知道,所以我们实际上插入删除有两步:

  1. 插入需要的数据;
  2. 对插入后的数据进行调整;

比如给出一个情景:
在这里插入图片描述
这里插入的 4 就很明显的破坏了堆的结构,我们小堆必须保证父节点 ≤ 子节点,那我就要做出调整,我们能用下标表示父节点与子节点的数学关系,让他和父节点进行比较再交换,换完观察现阶段结构是否满足,不满足继续换,我们把这种方法称之为:向上调整算法

堆的删除是删除堆顶的最大或最大值删除后,但依然需要每次调整堆的数据来满足结构,注意这么一个细节,我们删除是在堆顶删除!

栈顶删除后面子节点就会变成父节点,直接破坏了所有父子间关系,所以采用一般的挪动覆盖是不行的,其实我们根本不用抹去这个数,我们只需要把堆顶和堆尾元素交换,删除最后一个数据,然后再向下调整就行了。

首先为了方便,我们单独把交换功能写成一个函数接口;

void Swap(HPDataType* x1, HPDataType* x2){int tem;tem = x1;x1 = x2;x2 = tem;}

实现如下:

void AdjustDown(HPDataType* a, int n, int root){assert(a);int parent = root;int child = (parent/2)-1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;//找到子节点中较大的一个作为参与调整的子节点}if (a[child] > a[parent]){Swap(&a[child],&a[parent]);//不满足小堆就交换parent = child;child = parent * 2 + 1;}else{break;}}}

向上调整:

void AdjustUp(HPDataType* a, int child){assert(a);int parent = (child- 1)/2;while (child > 0)//不能用parent>=0判断,因为parent始终不小于0{if (a[parent] > a[child]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

到这里了咱光说不练假把式是吧,看看堆插入怎么搞:

void HeapPush(Heap* hp, HPDataType x){int i;assert(hp);if (hp->size == hp->capacity){hp->capacity *= 2;hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);//插入数据}else{hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a,hp->size-1);//调整堆数据}}

那么出堆也是同理:

void HeapPop(Heap* hp){assert(hp);Swap(hp->a[hp->size-1], hp->a[0]);hp->size--;AdjustDown(hp->a, hp->size,0);}

送上全部代码:
Heap.h

#pragma once#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}Heap;// 堆的构建void HeapCreate(Heap* hp, HPDataType* a, int n);// 堆的销毁void HeapDestory(Heap* hp);// 堆的插入void HeapPush(Heap* hp, HPDataType x);// 堆的删除void HeapPop(Heap* hp);// 取堆顶的数据HPDataType HeapTop(Heap* hp);// 堆的数据个数int HeapSize(Heap* hp);// 堆的判空int HeapEmpty(Heap* hp);

Heap.c

# define _CRT_SECURE_NO_WARNINGS #include"heap.h"void Swap(HPDataType* x1, HPDataType* x2){int tem;tem = x1;x1 = x2;x2 = tem;}void AdjustDown(HPDataType* a, int n, int root){assert(a);int parent = root;int child = (parent/2)-1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){Swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(HPDataType* a, int n, int child){assert(a);int parent = (child- 1)/2;while (parent>=0){if (a[parent] > a[child]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HeapCreate(Heap* hp, HPDataType* a, int n){assert(hp&& a);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);hp->size = n;hp->capacity = n;return hp;for (int i = 0; i < n; i++){hp->a[i] = a[i];}for (int i = (n - 2) / 2; i >=0 ; i-- ){AdjustDown(hp->a,hp->size,i);}}void HeapDestory(Heap* hp){assert(hp);free(hp->a);hp->a = NULL;hp->size = hp->capacity = 0;}void HeapPush(Heap* hp, HPDataType x){int i;assert(hp);if (hp->size == hp->capacity){hp->capacity *= 2;hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);}else{hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a,hp->size,hp->size-1);}}void HeapPop(Heap* hp){assert(hp);Swap(hp->a[hp->size-1], hp->a[0]);hp->size--;AdjustDown(hp->a, hp->size,0);}HPDataType HeapTop(Heap* hp){assert(hp);return hp->a[0];}int HeapSize(Heap* hp){assert(hp);return hp->size;}int HeapEmpty(Heap* hp){return hp->size == 0;}void HeapPrint(Heap* hp){assert(hp);int i;for (i = 0; i < hp->size; i++){printf("%s ", hp->a[i]);}}

在这里插入图片描述

调整算法的时间复杂度对比🤔

其实堆的插入与堆的删除时间复杂度都是一样的:logN,其实就是向上调整算法和向下调整算法的时间复杂度,最坏的情况下(即一直需要交换结点),需要循环的次数为:h - 1次(h为树的高度)。而h = log2(N+1)(N为树的总结点数),类比为二分搜索就很好理解,因此他和 qsort 是一个量级的。

在这里插入图片描述

建堆时间复杂度🤔

堆的本质是一棵完全二叉树,满二叉树是特殊的完全二叉树,我们就直接借满二叉树来计算就行了,建堆包含了调整算法,所以又分为向上调整建堆和向下调整建堆,这里就以向下调整建堆为例:
在这里插入图片描述
所以向下调整建堆时间复杂度就是:O(N)

同理,以错位相减法为运算基础,可得向上调整建堆时间复杂为:O(log N)

所以其实两种建堆是有差别的,但差别并不大。

在这里插入图片描述

堆排序🤔

堆排序是堆的一种实际运用,是利用堆对数据进行排序的操作,以大堆为例子(已建堆):
使用向下调整建堆要求左右子树都为堆,但要是不为堆呢?我们就要从倒数第一个非叶子节点开始向下调整,因为叶子节点既可以看成大堆也可以看成小堆,不需要向下调。

void Heapsort(int* a, int n){assert(a);//for(int i =1;i<n;i++)//{//AdjustUp(a, n, i);//使用向上调整建堆//}for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);//使用向下调整建堆倒着调整int tail = n - 1;while(tail>0){Swap(&a[0], &a[tail]);//前后交换AdjustDown(a, n, 0);//重新调整堆的结构tail--;}}

堆排序的时间复杂度为O(N*log N)

Topk问题🤔

Topk问题指的是找出堆中数据最大的 k 个或者最小的 k 个,比如守望先锋国服前十的仓鼠,CSDN 粉丝数前五的用户等等。找出 topk 元素的方法很简单就是用原数组建立一个大小为 k 的堆,再拿堆顶元素与k之后的元素比较,根据需求进行筛查,不符合就从堆中 pop 掉再插入对应的数组元素,到最后留下来的就是要找的 k 个元素。

//1. 找最大的K个元素//假设堆为小堆void SmallTopK(int* a, int n, int k){Heap hp;HeapCreate(&hp, a, n);int i;for (i = k; i < n; i++){if (a[i] > HeapTop(&hp)){HeapPop(&hp);HeapPush(&hp, a[i]);}//筛查,不符合条件的替换掉}for (i = 0; i <k; i++){printf("%d ", HeapTop(&hp));HeapPop(&hp);}}//2. 找最小的K个元素//假设堆为大堆void BigTopK(int* a, int n, int k){Heap hp;HeapCreate(&hp, a, n);int i;for (i = k; i < n; i++){if (a[i] < HeapTop(&hp)){HeapPop(&hp);HeapPush(&hp, a[i]);}for (i = 0; i < k; i++){printf("%d ", HeapTop(&hp));HeapPop(&hp);}}}

今天就到这里吧,摸了家人们。

在这里插入图片描述

手撕堆的实现(堆排序,Topk问题)——单手吊打数据结构 与50位技术专家面对面 手撕堆的实现(堆排序,Topk问题)——单手吊打数据结构 20年技术见证,附赠技术全景图