初阶数据结构之---堆的应用（堆排序和topk问题）
引言 上篇博客讲到了堆是什么，以及堆的基本创建和实现，这次我们再来对堆这个数据结构更进一步的深入，将讲到的内容包括：向下调整建堆，建堆的复杂度计算，堆排序和topk问题。话不多说，开启我们今天的内容吧。 堆排序 在讲堆排序之前，我想讲讲建堆的问题。在上篇博客中，我们建堆的时候是存在一个数组（数组中存储着我们建堆所需要的元素），通过一个个取出数组中的元素并插入新的堆中达到建...
【初阶数据结构】——堆排序和TopK问题
建堆插入数据向上调整算法建堆上篇文章中我们就实现了这个步骤，在主函数中创建了个数组然后将数组中的每个数据使用插入函数和向上调整算法函数依次插入动态开辟的空间中，每插入一个数据作为孩子和父亲相比较，根据大小交换位置，最终实现大/小堆。插入函数void HPPush(HP* php, HPDatatype x) { assert(php); if (php->size == php-&....
【数据结构】堆排序与TopK问题
1.堆的概念和结构堆的逻辑结构是完全二叉树。逻辑结构的视角观察：在大根堆中，双亲节点大于孩子节点；在小根堆中，双亲节点小于孩子节点。堆的存储结构是一维数组。 存储结构的视角观察（设数组K）：在小根堆中：K[i]<=K[2*i+1] && K[i]<=K[2*i+2]；在大根堆中：K[i]>=K[2*i+1] && K[i]>=K[2*i+2....
【数据结构与算法】堆的应用：堆排序和topk问题
一.堆排序我们知道冒泡算法的时间复杂度是O（N^2），在数据量很多的时候，N^2是个很可怕的数字，二分算法的时间复杂度是O(logn)，但是二分算法有限制条件，实用性并不高，那怎样才能高效实用的排序呢？堆排序就能很好解决上述问题，堆排序的时间复杂度是O(logn)，也没啥限制条件，可以实现高效排序。这里要注意，排升序要建大堆，排降序要建小堆;1.假设排升序，所以建大堆；2.堆建好后，定义一个 e....
数据结构-堆和堆排序-TopK问题
1.堆的定义堆是以二叉树的结构方式，所存储的一维数组。逻辑结构：二叉树物理结构：一维数组堆的特性：堆中某个节点的值总是不大于或不小于它的父亲节点的值。根结点值总是大于或等于其左右孩子结点的值，叫大根堆。根节点总是小于或等于其左右孩子结点的值，叫小根堆。堆总是一棵完全二叉树。如下图堆的示例：2.堆的实现接口（大堆）2.1 堆结构体定义使用一维数组来存储堆typedef int HPDataType....
【数据结构之二叉树简介·顺序存储·应用：堆·堆排序·TOPK问题】
前言前面一篇讲述了树，包括树的定义·相关概念和树的存储结构等，今天将讲述二叉树的的理论及相关应用·堆排序·TOPK问题。1.二叉树简介1.1二叉树定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。二叉树的特点：二叉树是每个结点最多有两个子树的树结构。即二叉树不允许存在度⼤于2的树。二叉树的子树有左右之分，其子树的次序不能颠倒。1.2现....
【数据结构】堆的拓展延伸 —— 堆排序 和 TopK问题
一、堆排序堆排序，是根据堆的结构而设计出的一种排序算法，其时间复杂度：O(N * logN)，空间复杂度：O(1)。堆排序的前提是需要 构建一个堆，而建堆有两种方法：向上调整建堆：上篇博客中，我们实现过 堆的向上调整算法。我们使用向上调整方法建堆时，需要复用堆的两个接口：初始化 和 插入(插入中调用了向上调整)。通过这种方法，我们可以建堆成功。那么它的时间复杂度怎么计算？对于 向上调整 来说，除....
【初阶数据结构】堆排序和TopK问题（下）
2-4完整代码#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef struct Heap { int* a; int size; int capacity; }HP; void HeapInit(HP* php) { ...
【初阶数据结构】堆排序和TopK问题（上）
1.堆的基本结构数据结构的堆和我们在操作系统里的堆不同，我们要讲的堆就是数据结构的堆。堆的逻辑结构（完全二叉树）和物理结构（数组）这里的堆是一个小根堆，（堆只分为大根堆和小根堆）ps:小根堆： 堆的逻辑结构（完全二叉树中）的任意一个结点值必须大于他的左孩子和右孩子的结点值,大根堆同理。值得注意的是这里即使是小根堆但依然不是有序的，通过小根堆我们能直接获取到的是最小值。PS：大小堆都只是父子之间的....
【数据结构】堆的应用 -- 堆排序和TopK问题
前言在开始这一节的内容之前，我们先来回顾一下与堆相关的重点：1、堆是二叉树顺序存储结构的一个具体体现，堆中每个节点的值总是不大于或不小于其父节点的值 (大堆/小堆)，堆总是一棵完全二叉树，堆使用顺序表存储元素；2、堆中父节点下标的计算公式：(n-1)/2，左孩子下标：n*2+1，右孩子下标：n*2+2；3、堆只能在尾部插入数据，且插入数据后需要保证堆的结构，所以在插入数据之后我们要进行向上调整，....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
算法编程
开发者社区在线编程频道官方技术圈。包含算法资源更新，周赛动态，每日一题互动。
+关注