牡丹江商城网站建设,深圳建设管理中心网站首页,wordpress微信登陆,湖南长沙门户网站文章目录前言堆的概念及结构堆初始化堆的判空堆的销毁插入数据删除数据堆的数据个数获取堆顶数据用数组创建堆对数组堆排序有关topk问题整体代码展示写在最后前言 #x1f6a9;前面了解了树#xff08;- 传送门 -#xff09;的概念后#xff0c;本章带大家来实现一…
文章目录前言堆的概念及结构堆初始化堆的判空堆的销毁插入数据删除数据堆的数据个数获取堆顶数据用数组创建堆对数组堆排序有关topk问题整体代码展示写在最后前言 前面了解了树- 传送门 -的概念后本章带大家来实现一个跟树有关的数据结构——堆本章有对堆排序和topk问题的讲解。 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把 堆 (一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 如下图 所以我们在实现 堆 的时候可以将它看作为一棵二叉树来思考这是它的 逻辑结构 。但其 物理结构 是一个实实在在的 顺序数组 (在内存当中存储的形式)。 那么接下来就开始实现一个属于自己的堆吧 堆的概念及结构 本章是以大堆为例只要会了大堆小堆也是不在话下。 堆是把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并且它的任意元素 Ki(i 0, 1, 2, 3, …, n - 1) 都满足 Ki K(i * 2 1) 且 Ki (i * 2 2) 或者 Ki K(i * 2 1) 且 Ki K(i * 2 2) 这样的堆我们称之为 小堆 或者 大堆 。我们还可以将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 有了对堆的概念和性质的理解相信大家对堆的元素是如何在数组中存储的物理结构明白了许多就是依照上面大堆小堆的概念来维持存储关系的。
图示 观察上图可知第一张图是一个大堆的逻辑结构和物理结构其每个结点的左右子结点都比这个结点要小或者等于第二张图是一个小堆的逻辑结构和物理结构其每个结点的左右子结点都比这个结点要大或者等于。所以一个堆他只能是小堆或者大堆不具有这两个堆的性质的都不属于堆下面我们来判断一下那些是堆那些不是堆
A. 100,60,70,50,32,65 // 这是一个大堆
B. 60,70,65,50,32,100 // 这不是堆
C. 65,100,70,32,50,60 // 这不是堆
D. 70,65,100,32,50,60 // 这不是堆
E. 32,50,80,70,65,100 // 这是一个小堆
F. 50,100,70,65,60,32 // 这不是堆其实如果想要更好的判断只需要将其逻辑结构画出来就一目了然了。 了解了堆的概念和结构后接下来就是实现啦 堆初始化
首先我们需要三个文件heap.hheap.ctest.c。heap.h用来存放所需头文件堆的结构体和相关函数声明。heap.c用来实现相关函数接口test.c用来测试。
下面是所需头文件
#include stdio.h
// assert断言所需
#include assert.h
// 动态内存开辟函数所需
#include stdlib.h
// bool类型所需
#include stdbool.h
// 拷贝函数所需
#include string.h我们知道堆的底层存储结构是一个顺序的数组因此这里需要跟前面我们实现的顺序表一样用动态内存空间。使用动态空间就需要一个变量来统计容量当然为了后面一些函数功能的需求还需要一个变量来统计堆的数据个数。因此一个堆的结构定义如下
// 堆的元素的数据类型
typedef int HPDataType;
typedef struct Heap
{// 指向存储数据的连续的空间数组HPDataType* a;// 统计当前堆中数据的个数int size;// 统计当前空间的容量int capacity;
}Heap;一个堆所需的函数接口声明如下
// 以大堆为例
// 堆初始化
void HeapInit(Heap* php);
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);// 插入数据
void HeapPush(Heap* php, HPDataType x);
// 删除数据
void HeapPop(Heap* php);// 获取堆顶数据
HPDataType HeapTop(Heap* php);// 获取堆数据个数
int HeapSize(Heap* php);// 堆判空
bool HeapEmpty(Heap* php);// 堆的销毁
void HeapDestroy(Heap* php);// 交换
void swap(HPDataType* a, HPDataType* b);
// 向上调整
void adjustup(HPDataType* a, int child);
// 向下调整
void adjustdown(HPDataType* a, int size, int parent);// 堆排序
void HeapSort(HPDataType* a, int n);
// topk问题
void PrintTopK(HPDataType* a, int n, int k);有了以上的铺垫堆的初始化就是将堆的结构里的指针置为空统计数据个数和统计空间容量的变量置为0即可。(当然也可以初始化的时候就开个初始空间)
相关函数接口功能的实现
// 堆初始化
void HeapInit(Heap* php)
{// 防止传递一个NULL上来传NULL的话php就是NULL后面的操作就不能进行了assert(php);php-a NULL;php-capacity php-size 0;
}堆的判空
有了统计堆的数据个数的变量size判空就简单多了。只需要判断一下size是否为0即可如果size为0说明为空返回true如果size不为0说明堆中有数据返回false。
相关函数接口功能的实现
// 堆判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}堆的销毁
堆的销毁也很简单将堆空间释放即可。当然size跟统计容量的capacity也置为0。
相关函数接口功能的实现
// 堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php-a);php-capacity php-size 0;
}插入数据 首先插入数据要看看容量够不够如果不够就需要扩容。 插入数据就是在数组的最后一个位置插入由于size是数据的个数也就是数组的长度所以size就是指向堆的最后一个数据的下一个位置因此我们只需要在size位置插入即可。当然插入过后多了一个数据因此size要自加1。 当我们插入数据之后现在堆的结构很可能就不是一个堆以大堆为例了因此这里需要对插入进来的那个数据执行一个向上调整的算法图示 对于向上调整算法我们需要找到这个结点假设下标为child的父亲结点假设下标为parent具体操作为parent (child - 1) / 2 找到父结点后就与他进行比较由于我们以大堆为例所以如果child位置上的数据大于parent位置上的数据就需要将这两个数据交换一下然后循环往复继续寻找父结点进行比较直到到达应该处在的位置为止直到是个堆为止。
相关函数接口功能的实现
// 插入数据
void HeapPush(Heap* 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 fail);exit(-1);}php-a tmp;php-capacity newcapacity;}// 在size位置插入数据然后size自加1php-a[php-size] x;// 对插入的那个数据执行向上调整算法重整堆// php-size - 1是插入的那个数据的下标adjustup(php-a, php-size - 1);
}向上调整算法
// 向上调整
void adjustup(HPDataType* a, int child)
{// 找父结点int parent (child - 1) / 2;while (child 0){// 如果child位置的数据大小大于parent位置的数据大小就交换if (a[child] a[parent]){// 交换swap(a[child], a[parent]);// 交换过后child依旧指向开始指向的那个数据child parent;// 继续找父结点parent (child - 1) / 2;}else break; // 如果小于等于了说明此时的堆是个真正的堆了直接跳出循环}
}这里有个swap函数其实现为
// 交换
// 注意是传递地址交换因为形参的改变不改变实参
void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp *a;*a *b;*b tmp;
}删除数据 删除数据其实是删除堆顶的数据由于堆是由一个数组来存放数据的那么我们该如何删除堆顶数组的第一个元素数据的数据呢 这里我们将堆顶数据和数组的最后一个数据交换一下然后size减一就实现了删除。 当然删除过后此时的堆已经不再是堆了所以我们需要对新的堆顶数据执行一下向下调整算法图示 对于向下调整算法我们先要找到该结点假设下标为parent的孩子结点而孩子结点又分为左孩子结点下标为parent * 2 1和右孩子结点下标为parent * 2 2所以我们需要找出两个孩子结点当中较大的那个如果该节点的数据比较大的那个孩子结点的数据要小那就进行交换然后循环往复继续向下寻找孩子结点重整堆。 整个操作我们可以先比较两个孩子的大小找出大的那个然后在与大的这个孩子结点进行比较如果父结点比他小以大堆为例说明这个孩子结点该上位了。然后继续向下执行这个操作。
相关函数接口功能的实现
// 删除数据删除堆顶的数据
void HeapPop(Heap* php)
{// 判断php的合法性并且要保证堆不为空空就不能删了assert(php !HeapEmpty(php));// 将堆的第一个数据与堆的最后一个数据交换swap(php-a[0], php-a[php-size - 1]);// size减一表示删除最后一个数据php-size--;// 对新的堆顶执行向下调整算法adjustdown(php-a, php-size, 0);
}向下调整算法
// 向下调整
void adjustdown(HPDataType* a, int size, int parent)
{// 先假设大的那个孩子结点为左孩子结点int child parent * 2 1;while (child size) // 如果child小于此时数组的长度就继续{// 第一个判断是防止没有右孩子结点的情况// 第二个判断是如果右孩子存在并且右孩子结点的数据大于左孩子结点的数据就child加一指向右孩子结点if (child 1 size a[child 1] a[child]) child;// 如果父节点数据小于child结点数据就交换重整堆if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else break; // 如果父节点数据大于child结点数据说明堆已经调整完毕直接跳出循环不在调整}
}堆的数据个数
由于我们定义了一个变量来统计堆的数据个数所以在这里只需要返回那个变量的值即可。
相关函数接口功能的实现
// 获取堆数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}获取堆顶数据 获取堆顶数据就是数组的第一个元素。 如果此时堆为空就不能获取了。
相关函数接口功能的实现
// 获取堆顶数据
HPDataType HeapTop(Heap* php)
{assert(php !HeapEmpty(php));return php-a[0];
}用数组创建堆 用数组创建堆就是将一个数组里面的所有元素拷贝到堆的数组里然后进行建堆。 我们首先开辟一个堆空间就是一段连续的数组长度与给的数组的长度相同然后将给的数组里的元素拷贝过来最后将堆里面的数据进行建堆。 如何建堆我们从最后一个结点的父节点开始依次执行向下调整算法直到根节点执行完全后便建成了堆。当然我们也可以从第二个结点开始依次执行向上调整算法直到最后一个结点执行完后便建成了堆不过这样的时间复杂度为O(n * logn)而前面的向下调整算法的方式的时间复杂度为O(n)所以这里我们采用向下调整算法的方式来建堆。至于这两个调整算法的时间复杂度是如何计算出来的这里就不做讨论它的本质其实是有关数列求和的计算。
向下调整算法方式建堆图示 有了上面的思路接下来就是代码实现了。
相关函数接口功能的实现
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{// php不能为NULLa不能为NULLassert(php a);// 开辟可存放n个数据的堆空间php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (php-a NULL){perror(malloc fail);exit(-1);}// 拷贝数据memcpy(php-a, a, sizeof(HPDataType) * n);php-size php-capacity n;// 从最后一个结点的父节点开始依次执行向下调整算法直到根结点执行完后结束// 这里i为什么初始化 (n - 2) / 2 呢 其实就是最后一个结点的父节点的下标// 前面说了寻找父节点的下标是 (child - 1) / 2// 这里是寻找最后一个结点的父结点而最后一个结点的下标是 (n - 1)n是数组长度// 所以它的父节点就是 (n - 1 - 1) / 2 , 也就是(n - 2) / 2for (int i (n - 2) / 2; i 0; i--) adjustdown(php-a, n, i);
}对数组堆排序 有了建堆的认识堆排序也不难只不过需要注意几个细节。 对数组排序首先就是要对这个数组建堆如果是要将数组升序就建为大堆如果是要将数组降序就建为小堆为什么呢这里以升序为例进行讲解弄懂了升序降序也只是大于小于号的问题了。 当数组建成大堆形式后同样的使用向下调整算法建堆堆顶元素是最大的此时我们可以将堆顶元素与最后一个元素进行交换这样最大的元素就到了数组的末尾了。然后我们对这个处在数组最后一个位置的最大元素视而不见将交换过去的堆顶元素执行向下调整算法这时第二大的元素就到了堆顶然后此时的堆顶元素继续与最后一个元素进行交换 注意第一个交换过去的最大的元素已经不在范围内了也就是说每将一个当前最大的数交换过去后可视作size减一一次 然后再将交换过去的堆顶元素执行向下调整算法…这样循环往复最终该数组就变成了升序。 相关函数接口功能的实现
// 堆排序
void HeapSort(HPDataType* a, int n)
{assert(a);// 向下调整, 这里是建大堆for (int i (n - 2) / 2; i 0; i--) adjustdown(a, n, i);// 排序建的大堆就是升序int k n - 1;while (k 0){swap(a[0], a[k]);adjustdown(a, k, 0);k--;}
}有关topk问题 如何在百万个成绩数据里面找出前十个最好的这就是典型的topk问题。可以看到它需要处理的数据非常多当然也有的很少不过面试一般就是问多的情况让你找出前k个最那啥的因此这里需要用到堆来解决。 为什么堆可以解决呢堆的堆顶要么是整个堆里最大的元素要么是整个堆里最小的元素。根据这一性质假如求很多数据中前k个最小的数据我们可以先开辟一个堆空间该堆空间可以存放k个数据然后我们将很多数据中的前k个数据拷贝进堆里并将其建成大堆此时堆的堆顶元素就是堆里所有元素最大的那一个接着我们从很多数据的第k个数开始遍历这些数据如果该数据小于此时堆顶的数据就将堆顶数据更新为这个小的数据然后对其执行向下调整算法执行完过后堆顶还是堆中最大的那个元素就这样判断并操作直到遍历结束堆中就是那前k个最小的数啦。最后将这些数打印即可。找前k个最小的数就是建大堆反之建小堆这里就不作讨论了 原理以求前k个最小的数为例每次比堆顶小的元素入堆并调整后之前堆中最大的元素被抛弃新的最大的元素上位了这样循环往复下去每次操作除大的进小的当然最后堆中就是前k个最小的数啦。
相关函数接口功能的实现
// topk问题
void PrintTopK(HPDataType* a, int n, int k)
{assert(a);// 开辟能够存放k个数据的堆空间HPDataType* topk (HPDataType*)malloc(sizeof(HPDataType) * k);if (topk NULL){perror(malloc fail);exit(-1);}// 拷贝前k个数据进堆memcpy(topk, a, sizeof(HPDataType) * k);// 找前k个最小的建大堆for (int i (k - 2) / 2; i 0; i--) adjustdown(topk, k, i);// 对topk堆进行 除大的进小的 操作for (int i k; i n; i){if (a[i] topk[0]){topk[0] a[i];// 每次进来一个较小的元素都要执行一遍向下调整算法来调整堆adjustdown(topk, k, 0);}}// 打印 topkfor (int i 0; i k; i) printf(%d , topk[i]);// 最后使用完堆后记得释放free(topk);
}整体代码展示
heap.h
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h
#include string.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;// 以大堆为例
// 堆初始化
void HeapInit(Heap* php);
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);// 插入数据
void HeapPush(Heap* php, HPDataType x);
// 删除数据
void HeapPop(Heap* php);// 获取堆顶数据
HPDataType HeapTop(Heap* php);// 获取堆数据个数
int HeapSize(Heap* php);// 堆判空
bool HeapEmpty(Heap* php);// 堆的销毁
void HeapDestroy(Heap* php);// 交换
void swap(HPDataType* a, HPDataType* b);
// 向上调整
void adjustup(HPDataType* a, int child);
// 向下调整
void adjustdown(HPDataType* a, int size, int parent);// 堆排序
void HeapSort(HPDataType* a, int n);
// topk问题
void PrintTopK(HPDataType* a, int n, int k);heap.c
#include heap.h// 堆初始化
void HeapInit(Heap* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{assert(php a);php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (php-a NULL){perror(malloc fail);exit(-1);}memcpy(php-a, a, sizeof(HPDataType) * n);php-size php-capacity n;for (int i (n - 2) / 2; i 0; i--) adjustdown(php-a, n, i);
}// 插入数据
void HeapPush(Heap* 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 fail);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;adjustup(php-a, php-size - 1);
}
// 删除数据删除堆顶的数据
void HeapPop(Heap* php)
{assert(php !HeapEmpty(php));swap(php-a[0], php-a[php-size - 1]);php-size--;adjustdown(php-a, php-size, 0);
}// 获取堆顶数据
HPDataType HeapTop(Heap* php)
{assert(php !HeapEmpty(php));return php-a[0];
}// 获取堆数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}// 堆判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}// 堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php-a);php-capacity php-size 0;
}// 交换
void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp *a;*a *b;*b 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 (child - 1) / 2;}else break;}
}
// 向下调整
void adjustdown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size 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(HPDataType* a, int n)
{assert(a);// 向下调整, 这里是建大堆for (int i (n - 2) / 2; i 0; i--) adjustdown(a, n, i);// 排序建的大堆就是升序int k n - 1;while (k 0){swap(a[0], a[k]);adjustdown(a, k, 0);k--;}
}// topk问题
void PrintTopK(HPDataType* a, int n, int k)
{assert(a);HPDataType* topk (HPDataType*)malloc(sizeof(HPDataType) * k);if (topk NULL){perror(malloc fail);exit(-1);}memcpy(topk, a, sizeof(HPDataType) * k);// 找前k个最小的建大堆for (int i (k - 2) / 2; i 0; i--) adjustdown(topk, k, i);for (int i k; i n; i){if (a[i] topk[0]){topk[0] a[i];adjustdown(topk, k, 0);}}for (int i 0; i k; i) printf(%d , topk[i]);free(topk);
}test.c
#include heap.hvoid test1()
{Heap hp;HeapInit(hp);HeapPush(hp, 22);HeapPush(hp, 122);HeapPush(hp, 16);HeapPush(hp, 45);HeapPush(hp, 56);HeapPush(hp, 18);HeapPush(hp, 134);HeapPush(hp, 99);HeapDestroy(hp);
}void test2()
{Heap hp;HeapInit(hp);int arr[] { 34,113,78,44,98,99,35,26,18,68 };int n sizeof(arr) / sizeof(arr[0]);HeapCreateArray(hp, arr, n);while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}printf(\n);HeapDestroy(hp);
}void test3()
{int arr[] { 34,113,78,44,98,99,35,26,18,68 };int n sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);for (int i 0; i n; i) printf(%d , arr[i]);printf(\n);
}void testTopK()
{int arr[] { 34,113,78,44,98,99,35,26,18,68 };int n sizeof(arr) / sizeof(arr[0]);PrintTopK(arr, n, 5);
}int main()
{//test1();test2();test3();testTopK();return 0;
}写在最后 ❤️后续将会持续输出有关数据结构与算法的文章你们的支持就是我写作的最大动力 感谢阅读本小白的博客错误的地方请严厉指出噢~
