【数据结构和算法初阶(C语言)】二叉树的顺序结构--堆的实现/堆排序/topk问题详解---二叉树学习日记②

目录

编辑

1.二叉树的顺序结构及实现

1.1 二叉树的顺序结构

2 堆的概念及结构

3 堆的实现

3.1堆的代码定义

3.2堆插入数据

3.3打印堆数据

3.4堆的数据的删除

3.5获取根部数据

3.6判断堆是否为空

3.7 堆的销毁

4.建堆以及堆排序

4.1 升序建大堆，降序建小堆

4.2堆排序

4.3 topk问题

5.结语

1.二叉树的顺序结构及实现

1.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

左孩子的下标 = 父亲下标*2+1

右孩子下标 = 父亲节点下标*2+2

父亲节点下标 = （子节点下标-1）/2

2 堆的概念及结构

堆是非线性结构，是完全二叉树

如果有一个值的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

通俗来说父节点小于等于子节点的完全二叉树就叫小根堆，或者小堆，根一定是整棵树最小的。

父节点值大于等于子节点的完全二叉树叫做大根堆。或者大堆，但是底层数组不一定降序。但是大堆的根是整棵树的最大值。

3 堆的实现

3.1堆的代码定义

底层是一个顺序表

typedef int HPDataType;typedef struct Heap
{//底层是一个顺序表，但是数据不是随便存储，逻辑结构是二叉树HPDataType * a;int size;int capacity;
}HP;

堆的初始化：

void HeapInit(HP* php)
{assert(php);HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * 2);//先为i堆空间申请两个节点if (tmp == NULL){perror("malloc");exit(-1);}php->a = tmp;php->capacity = 2;php->size = 0;
}

3.2堆插入数据

实现关键

实现原理图：向上调整：

（以大堆的实现方式举例）

首先我们从有限个数据的层面来实现一下堆的实现，后面堆排序再来看对于一堆数据怎么建堆。

对于一组少量数据比如一个数组：

首先将数据一个一个插入到堆里面，由于数据有限可以使用这种数据插入的方式建立堆这种数据结构；

void HeapPush(HP* php, HPDataType x)
{//尾插assert(php);//判断空间够不够if (php->capacity == php->size){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(php->a) + sizeof(HPDataType) * 2);if (tmp == NULL){perror("realloc");exit(-1);}php->a = tmp;php->capacity += 2;}php->a[php->size] = x;php->size++;//调整数据，变成堆AdjustUp(php->a, php->size-1);}

然后把这组数据调整成一个堆：

void Swap(HPDataType* child, HPDataType* parent)
{HPDataType tmp = 0;tmp = *child;*child = *parent;*parent = 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;//跳出循环}}}

3.3打印堆数据

为了看一下我们插入的效果我们来试一下插入一段数据

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

就建成了一个大堆。

3.4堆的数据的删除

堆这个数据结构有意义的一个点就是，大堆的根一定是这组数据中最大的值，小堆的根一定是这组数据中最小的值。所以如果我们能拿到这个根的数据，再删除就可以找到这堆数据中次小的数据了。那么删除根数据是这个结构比较有意义的。

想一个问题：根的删除能不能简单的数据覆盖？只是将后续的数据移动向前

答案是不能的，可以数据这样移动后续数据根本就不能成堆了。那么这里使用的方法是向下调整法

前提是左右子树是堆：

这里我们以小堆举例示范：

先删除

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

在调整

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+1可能越界访问{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else{break;}}}

调整是由于每次都是取两个子节点中的较小的值，所以先假设一个大，如果假设错了，就改变下标

if (child+1<n&&a[child + 1] < a[child])//child+1可能越界访问
       {
           child++;
       }

对调整循环结束的判定所示孩子下标小于n

3.5获取根部数据

//获取根部数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

3.6判断堆是否为空


//判断堆是否为空函数
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;}

3.7 堆的销毁

void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

那么如果现在我们每次拿到堆的元素在删除在获取，就可以得到一个有序的数据了：

4.建堆以及堆排序

上面我们已经掌握了堆这个数据结构的一些方法，最后通过插入数据建堆。删除1数据将数据排序。可是如果我有十亿个数据，想找出最大的十个数据，如果用堆得插入10亿次数据吗？那就失去了使用这个数据结构的意义，通常来说我们只用建立一个大堆模型，这个堆的前十个数据自然就是10亿个数据中的最大的一个。

4.1 升序建大堆，降序建小堆

4.2堆排序

4.3 topk问题

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，

基本思路如下：

1. 用数据集合中前K个元素来建堆前k个最大的元素，则建小堆前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

（明天补）

5.结语

以上就是本期的所有内容，知识含量蛮多，大家可以配合解释和原码运行理解。创作不易，大家如果觉得还可以的话，欢迎大家三连，有问题的地方欢迎大家指正，一起交流学习，一起成长，我是Nicn，正在c++方向前行的奋斗者，数据结构内容持续更新中，感谢大家的关注与喜欢。