C语言怎么实现堆及堆的结构与接口

本文小编为大家详细介绍“C语言怎么实现堆及堆的结构与接口”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言怎么实现堆及堆的结构与接口”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。在现实中我们通常把堆 (一种完全二叉树) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。堆总是满足下列性质：堆中某个结点的值总是不大于或不小于其父结点的值；堆总是一棵完全二叉树。堆是非线性数据结构，相当于一维数组，有两个直接后继。【大根堆和小根堆】：根结点最大的堆叫做大根堆，树中所有父亲都大于或等于孩子。根结点最小的堆叫做小根堆，树中所有父亲都小于或等于孩子。【思考】这个大根堆和小根堆有什么特点呢？最值总在 0 号位，根据这个特点我们就可以做很多事情，比如TopK问题 (在一堆数据里面找到前 K 个最大 / 最小的数)，生活中也有很多实例，比如点餐软件中有上千家店铺，我想选出该地区好评最多的十家川菜店，我们不用对所有数据排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。下面给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：该节点的左右子树必须是一个 (大 / 小) 堆，才能调整。上面的数组，因为根节点的左右子树都是小堆，所以我们从根节点开始调整，将其调成小堆。向下调整算法思路（调成小堆）：从根节点开始，不断往下调。选出根节点的左右孩子中「最小的孩子」，与「父亲」进行比较。如果父亲小于孩子，就不需处理了，整个树已经是小堆了。如果父亲大于孩子，就跟父亲交换位置，并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。向下调整算法过程演示（调成小堆，把大的节点往下调整）：向下调整算法代码：我们以满二叉树计算，最坏情况下，向下调整算法最多进行满二叉树的高度减1次比较，则说明向下调整算法最多调整满二叉树的高度减1次，n 个节点的满二叉树高度为 log2(n+1)，估算后所以时间复杂度为 O(log2n)。下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆，我们需要通过算法把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆，我们应该怎么调整呢？我们倒着调整，从下到上，从「倒数第一个非叶子节点的子树」开始，依次遍历完所有非叶子节点，分别对每个子树进行「向下调整」成 (大 / 小) 堆，一直调整到「根节点」，就可以建成一个 (大 / 小) 堆。为什么要倒着调整呢？因为这样我们可以把「倒数第一个非叶子节点的子树」的左右子树看成是一个 (大 / 小) 堆，此时才能去使用向下调整算法。比如下图中的黄色填充的子树，3 的左子树 6 就可以看成是一个大堆。【实例】：将下面的数组建成一个大堆建堆过程演示（以建大堆为例）：从下到上，依次遍历完所有非叶子节点，分别对每个子树进行向下调整。依次对 每一步 中，方框内的树 进行 向下调整 为一个 大堆。建堆代码：排升序 –> 建大堆：【思考】排升序，建小堆可以吗？– 可以是可以，但没啥意思。首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第2小的数，不断重复上述过程……。建 n 个数的堆时间复杂度是O(N)，所以上述操作时间复杂度为O(N2)，效率太低，尤其是当数据量大的时候，效率更低，同时堆的价值没有被体现出来，还不如用直接排序。【最佳方法】排升序，因为数字越来越大，需要找到最大的数字，得建大堆首先对 n 个数建大堆。将最大的数（堆顶）和最后一个数交换，把最大的数放到最后。前面 n-1 个数的堆结构没有被破坏（最后一个数不看做堆里面的），根节点的左右子树依旧是大堆，所以我们进行一次向下调整成大堆即可选出第2大的数，放到倒数第二个位置，然后重复上述步骤……。【时间复杂度】：建堆时间复杂度为O(N)，向下调整时间复杂度为O(log2N)，这里我们最多进行N-2次向下调整，所以堆排序时间复杂度为O(N*log2N)，效率是很高的。排降序 –> 建小堆：【最佳方法】排降序，因为数字越来越小，需要找到最小的数字，得建小堆首先对 n 个数建小堆。将最小的数（堆顶）和最后一个数交换，把最小的数放到最后。前面 n-1 个数的堆结构没有被破坏（最后一个数不看做堆里面的），根节点的左右子树依旧是小堆，所以我们进行一次向下调整成小堆即可选出第2小的数，放到倒数第二个位置，然后重复上述步骤……。【时间复杂度】：建堆时间复杂度为O(N)，向下调整时间复杂度为O(log2N)，这里我们最多进行N-2次向下调整，所以堆排序时间复杂度为O(N*log2N)，效率是很高的。因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明，计算起来比较好算(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：建堆要从倒数第一个非叶子节点开始调整，也即是从倒数第二层开始调，可得出时间复杂度公式：T ( n ) = ∑ ( 每 层 节 点 数 ∗ ( 堆 的 高 度 − 当 前 层 数 ) )所以，建堆的时间复杂度为O(N)。【上面学了那么多，这里小小总结一下】堆的向下调整算法就是，在该节点左右子树都是一个小/大堆的前提下，将以该节点为根的树调整成一个小/大堆。堆的创建就是倒着调整，从下到上，从倒数第一个非叶子节点的子树开始，依次遍历完所有子树，分别对其进行向下调整。时间复杂度：堆的向下调整算法为O(log2N)，堆的创建为O(N)。首先新建一个工程（ 博主使用的是 VS2019 ）Heap.h（堆的类型定义、接口函数声明、引用的头文件）Heap.c（堆接口函数的实现）Test.c（主函数、测试堆各个接口功能）Heap.h 头文件代码如下：堆的初始化，首先需要实现一个向下调整算法：堆的初始化代码：先插入一个新元素到数组的尾上，从插入的新元素开始，进行向上调整算法，直到满足（大/小）堆。堆的插入过程演示：堆的插入，首先需要实现一个向上调整算法：堆的插入代码：将堆顶元素和最后一个元素交换（这免费云主机域名样就变成尾删了，很方便）删除堆中最后一个元素从根节点开始，对剩下元素进行向下调整，调成（大/小）堆堆的删除过程演示：堆的插入，首先需要实现一个向下调整算法：前面已经实现过了，这里就不展示了。堆的删除代码：堆的相关接口实现好了，因为是大堆，所以我们可以很方便的来找出堆中前 k 个最大元素。这里要和前面的堆排序区分开哦，这里我们并不是在堆中对所有元素排好序。运行结果：下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆，我们需要通过「向上调整算法」把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆，我们应该怎么调整呢？我们从上到下，从「第一个节点（也就是根节点）的左孩子」开始，依次遍历完所有节点，分别对每个节点进行「向上调整」，一直到「最后一个节点」，就可以建成一个 (大 / 小) 堆。我们把数组中的「第一个元素」看作是一个「堆」，剩余的元素依次插入到这个「堆」中。前面我们也实现了堆的插入接口，原理就是向上调整。读到这里，这篇“C语言怎么实现堆及堆的结构与接口”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注百云主机行业资讯频道。

相关推荐: jquery点击怎么实现升序降序图标切换

这篇文章主要讲解了“jquery点击怎么实现升序降序图标切换”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“jquery点击怎么实现升序降序图标切换”吧！需求: 有一个查询结果,返回的是表格的形式,点击表头任何一…