数据结构与算法⑬(第四章_中_续二)堆解决Topk问题+堆的概念选择题
TopK问题介绍： TOP-K问题：即求数据中找出前K个最大的元素或者最小的元素，一般情况下数据量都比较大。 在N个数中找出最大/小的前K个 （比如在1000个数中找出最大/小的前10个） 以前的方法：冒泡排序。时间复杂度： O(N^2) 现在找最大的k个数的方法： 方法1：堆排序降序，前N个就是最大的。上篇学过时间复杂度： O(N*logN) 方...
初阶数据结构之---堆的应用（堆排序和topk问题）
引言 上篇博客讲到了堆是什么，以及堆的基本创建和实现，这次我们再来对堆这个数据结构更进一步的深入，将讲到的内容包括：向下调整建堆，建堆的复杂度计算，堆排序和topk问题。话不多说，开启我们今天的内容吧。 堆排序 在讲堆排序之前，我想讲讲建堆的问题。在上篇博客中，我们建堆的时候是存在一个数组（数组中存储着我们建堆所需要的元素），通过一个个取出数组中的元素并插入新的堆中达到建...
数据结构——堆的应用 Topk问题
解题思路 正常思路 将这N个数建成一个大堆，然后Popk次，就可以找出最大的前k个 ； 但是如果N非常大以亿计（10亿个整数所占空间大概4G）那么就会非常耗时耗力，难以计算。 这里给出一种更好的解决办法： ①将前k个数建成小堆；（必须是小堆哦~） ②后面N-k个数依次比较，如果比堆顶的数据大，就替换它进堆； ...
【初阶数据结构】——堆排序和TopK问题
建堆插入数据向上调整算法建堆上篇文章中我们就实现了这个步骤，在主函数中创建了个数组然后将数组中的每个数据使用插入函数和向上调整算法函数依次插入动态开辟的空间中，每插入一个数据作为孩子和父亲相比较，根据大小交换位置，最终实现大/小堆。插入函数void HPPush(HP* php, HPDatatype x) { assert(php); if (php->size == php-&....
玩转堆排序以及Topk问题——【数据结构】
学习了二叉树以及堆，今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。在学习开始我们先来回顾一下上篇博客中我们提到的堆，在实现堆时我们要进行向上调整或向下调整来继续保存堆的特性。具体代码如下：向上调整函数：void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child...
【数据结构】堆排序与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,堆排序, --堆的初始化与应用
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。个人主页：主页链接算法专栏：专栏链接 我会一直往里填充内容哒！LeetCode专栏：专栏链接目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出代码仓库：Gitee链接点击关注=收获更多优质内容书接上回,本章节也是关于树的内....
【数据结构与算法】堆的应用：堆排序和topk问题
一.堆排序我们知道冒泡算法的时间复杂度是O（N^2），在数据量很多的时候，N^2是个很可怕的数字，二分算法的时间复杂度是O(logn)，但是二分算法有限制条件，实用性并不高，那怎样才能高效实用的排序呢？堆排序就能很好解决上述问题，堆排序的时间复杂度是O(logn)，也没啥限制条件，可以实现高效排序。这里要注意，排升序要建大堆，排降序要建小堆;1.假设排升序，所以建大堆；2.堆建好后，定义一个 e....
数据结构---TopK和堆排序
向下调整算法 首先声明这个算法的使用条件，该算法适用于除了堆顶外的其他部分都满足小堆或大堆的条件时，可以使用，简单来说就是pop堆顶的时候可以使用 使用的原理也相当简单，假设我们这里是小堆，那么堆顶元素被弹出，此时堆中第二小的元素一定是这个堆顶元素的儿子，那么我们就让堆的最后一个叶子来充当这个新的堆顶，这样可以在保持堆整体的构造不变的前提下还能把堆顶元素弹出，紧接着就让这个堆顶元素和下面的儿...
数据结构-堆和堆排序-TopK问题
1.堆的定义堆是以二叉树的结构方式，所存储的一维数组。逻辑结构：二叉树物理结构：一维数组堆的特性：堆中某个节点的值总是不大于或不小于它的父亲节点的值。根结点值总是大于或等于其左右孩子结点的值，叫大根堆。根节点总是小于或等于其左右孩子结点的值，叫小根堆。堆总是一棵完全二叉树。如下图堆的示例：2.堆的实现接口（大堆）2.1 堆结构体定义使用一维数组来存储堆typedef int HPDataType....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
算法编程
开发者社区在线编程频道官方技术圈。包含算法资源更新，周赛动态，每日一题互动。
+关注