精华内容
下载资源
问答
  • 堆排序解决topk问题
    2017-01-08 13:20:42
    import time
    import heapq
    import random
    
    def gen_large_arr(n):
        arr = [i for i in range(n)]
        random.shuffle(arr)
        return arr
    
    # find top n item from bigarray using liner search
    def liner_search(bigarray, n):
        return sorted(bigarray, reverse=True)[:n]
    
    # using heap sort
    def heap_search(bigarray, n):
        heap = []
        for elem in bigarray:
            if len(heap) < n or elem > heap[0]:
                if len(heap) == n:
                    heapq.heappop(heap)
                heapq.heappush(heap, elem)
    
        return heap
    
    
    start = time.time()
    bigarray = gen_large_arr(10 * 1000 * 1000)
    print 'gen arr took %g s' % (time.time() - start)
    
    start = time.time()
    print liner_search(bigarray, 10)
    print 'linear search took %g s' % (time.time() - start)
    
    start = time.time()
    print heap_search(bigarray, 10)
    print 'heap search took %g s' %(time.time() - start)
    
    更多相关内容
  • 教你用堆排序解决topk问题,同时学会堆排序。 1、什么是Top K问题? 找到数组中最大(最小)的K个数,例如7,6,3,5,2,Top3 的意思就是 找出最小的三个数即为:3,5,2。 方法1:对数组全部排序,然后根据要求取其中K...

    教你用堆排序解决topk问题,同时学会堆排序。

    1、什么是Top K问题?

    找到数组中最大(最小)的K个数,例如7,6,3,5,2,Top3 的意思就是 找出最小的三个数即为:3,5,2。

    • 方法1:对数组全部排序,然后根据要求取其中K个数
    • 方法2:只对K个排序,例如冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒k个泡,就得到TopK。
    • 方法3:就是本文主要要讲的堆,构建一个大顶堆(小顶堆),然后堆顶就是最大值(最小值)取出最大值后调整堆,再继续取堆顶值,取到k为止。

    看完了topk的问题,我们现在看看怎么用堆来解决这个问题。首先让我们一起来看看堆是一种什么样的数据结构。

    2、什么是堆?

    • a、它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的。注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树。
      在这里插入图片描述

    • b、堆中的每一个节点的关键字都大于(或等于)这个节点的子节点的关键字。

    3、怎么用完全二叉树表示数组?

    那好,如果给你定你一个数组:[9, 4, 5, 7, 6, 8] 转换成完全二叉树。那么转换后的结构如下图所示:

    那我们可以看到这个完全二叉树不满足前面堆的定义:每一个节点的关键字都大于(或等于)这个节点的子节点的关键字。也就是父节点要大于子节点。这种用数组实现的二叉树,假设节点在数组中的索引值为index,那么:

    • 节点的左子节点是 2*index+1,

    • 节点的右子节点是 2*index+2,

    • 节点的父节点是 (index-1)/2。

    例如数组中的4,它在数组中的index为1。左子节点7的index值为3=2x1+1,右子节点6的index值为4=2x1+2。上图中的完全二叉树不是堆结构,那么我们要怎么对它调整变成堆呢?下面就看一下怎么调整完全二叉树变成堆。

    4、怎么使完全二叉树变成堆?

    我们假设上图中的4进行调整,因为4没有它的子节点值大。如下图所示:

    在这里插入图片描述

    我需要将4和7的位置进行一个互换,才能满足堆的性质。交换之后如果说4就变成了7.如果7的父节点比7小就要再次调整,本例子中由于由于不比父节点大,所以不用再次调整。那如果我们将这个操作封装成一个函数要怎么操作呢?

    func AdjustHeap(array []int, length, i int) {
    	//调整第i个元素
    	if i > length {//终止条件
    		return
    	}
    	max := i
    	c1 := 2*i + 1 //左子节点index值
    	c2 := 2*i + 2 //右子节点index值
        //和两个子节点进行比较,取3个当中的最大值所在的index值
    	if c1 < length && array[max] < array[c1] {
    		max = c1
    	}
    	if c2 < length && array[max] < array[c2] {
    		max = c2
    	}
    	if max != i {//父节点不是最大,就要和其中的一个子节点进行交换
    		array[i], array[max] = array[max], array[i]
    		AdjustHeap(tree, length, max) //对交换后的那个元素再次调整,因为可能使得上一层或者下一层不满足堆的性质
    	}
    }
    

    5、怎么构造堆?

    从第一个非叶子结点从下至上,从右至左调整结构。本题第一个非叶子节点也就是4,第二个是5。那么第一个非叶子节点它的index值是多少呢?

    index = (length-1)/2 - 1
    

    只需要将这个index 递减至0的进行一次循环调用调整堆的函数,就最终将一个完全二叉树变成了一个大顶堆的结构。

     //从第一个非叶子结点从下至上,从右至左调整结构
     func BuildHeap(tree []int, length int) {
    	for i := (length-1)/2 - 1; i >= 0; i-- {
    		AdjustHeap(tree, length, i)
    	}
    }
    

    本例题中调整完之后变成下图所示的结果。

    在这里插入图片描述

    注意数组中的数字变化,此时仍然没有满足有序。但是第一个数变成了最大值,也就是我们所说的大顶堆。

    6、利用大顶堆排序

    堆排序只需要来一个倒序遍历,每次将第一个元素移到最后就可以了。交换的同时,重新调整大顶堆。

    func HeapSort(array []int) {
    	BuildHeap(array, len(array)) //构造大顶堆
    	for i := len(array) - 1; i >= 0; i-- {
    		array[i], array[0] = array[0], array[i] //将最大值和最后一个元素互换,最后一个元素就变成了最大值
    		AdjustHeap(array, i, 0) //第一个元素已经变化,需要重新调整使之重新变为大顶堆        
    	}
    }
    

    那么如果是topk的问题,只需要循环k次即可,后面K个元素就是有序的了。

    7、例题巩固

    给定String类型的数组strArr,再给定整数k,请严格按照排名顺序打印 出次数前k名的字符串。

    [要求]

    如果strArr长度为N,时间复杂度请达到O(N \log K)O(NlogK)

    输出K行,每行有一个字符串和一个整数(字符串表示)。
    你需要按照出现出现次数由大到小输出,若出现次数相同时字符串字典序较小的优先输出

    示例 输入

    ["1","2","3","4"],2
    

    样例返回值

    [["1","1"],["2","1"]]
    

    参考答案:

    func topKstrings(strings []string, k int) [][]string {
    	// write code here
    	result := [][]string{}
    	//统计频次
    	resMap := map[string]int{}
    	for _, v := range strings {
    		resMap[v]++
    	}
    	length := len(strings)
    
    	//构建堆
    	for i := (length-1)/2 - 1; i >= 0; i-- {
    		AdjustHeap(resMap, strings, length, i)
    	}
    	fmt.Print(strings)
    
    	//输出结果
    	for i := length - 1; i >= 0; i-- {
    		strings[i], strings[0] = strings[0], strings[i]
    		//保存结果
    		t := []string{strings[i]}
    		feq := strconv.Itoa(resMap[strings[i]])
    		t = append(t, feq)
    		result = append(result, t)
    		if len(result) >= k {
    			return result
    		}
    		AdjustHeap(resMap, strings, i, 0)
    	}
    	return result
    }
    
    func AdjustHeap(resMap map[string]int, result []string, length, i int) {
    	if i > length {
    		return
    	}
    	max := i
    	c1 := 2*i + 1
    	c2 := 2*i + 2
    	if c1 < length {
    		if resMap[result[c1]] > resMap[result[max]] {
    			max = c1
    		} else if resMap[result[c1]] == resMap[result[max]] && result[c1] < result[max] {
    			max = c1
    		}
    	}
    	if c2 < length {
    		if resMap[result[c2]] > resMap[result[max]] {
    			max = c2
    		} else if resMap[result[c2]] == resMap[result[max]] && result[c2] < result[max] {
    			max = c2
    		}
    	}
    	if max != i {
    		result[i], result[max] = result[max], result[i]
    		AdjustHeap(resMap, result, length, max)
    	}
    }
    

    参考资料:

    1、https://www.bilibili.com/video/BV1Eb41147dK?t=1568

    2、https://www.nowcoder.com/practice/fd711bdfa0e840b381d7e1b82183b3ee?tpId=117&&tqId=35559&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

    展开全文
  • 上次介绍了堆排序,这次介绍堆排序常见的应用场景TopK问题。利用堆求TopK问题TopK问题是一个堆排序典型的应用场景。题目是这样的:假设,我们想在大量的数据,如 100 亿个整型数据中,找到值最大的 K 个元素,K 小于...

    670a4ce6196543cdbf61427cbd955bbd.png

    上次介绍了堆排序,这次介绍堆排序常见的应用场景TopK问题。

    利用堆求TopK问题TopK问题是一个堆排序典型的应用场景。

    题目是这样的:假设,我们想在大量的数据,如 100 亿个整型数据中,找到值最大的 K 个元素,K 小于 10000。对此,你会怎么做呢?

    对标的是Leetcode第215题:「数组中的第K个最大元素。」

    具体链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    示例 1:

    输入: [3,2,1,5,6,4] 和 k = 2

    输出: 5

    示例 2:

    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

    输出: 4

    经典的TopK问题还有:最大(小) K 个数、前 K 个高频元素、第 K 个最大(小)元素

    对此TopK问题本质上是一个排序问题,排序算法一共有十个,这个还有很多排序算法没有介绍过。

    9c6d04a82b237a8f4f88686fb8d6b718.png

    至于为什么TopK问题最佳的答案是堆排序?其实在空间和时间的复杂度来考量,虽说快排是最好的排序算法,但是对于100亿个元素从大到小排序,然后输出前 K 个元素值。

    可是,无论我们掌握的是快速排序算法还是堆排序算法,在排序的时候,都需要将全部的元素读入到内存中。也就是说,100亿个整型元素大约需要占用40GB的内存空间,这听起来就不像是普通民用电脑能干的事情,(一般的民用电脑内存比这个小,比如我写文章用的电脑内存是 32GB)。

    众所周知,快速排序和堆排序的时间复杂度都可以达到,但是对于快速排序来说,数据是顺序访问的。而对于堆排序来说,数据是跳着访问的。比如堆排序中,最重要的一个操作就是数据的堆化。因此,快速排序的时间复杂度是优于堆排序的。

    但是快速排序是新建数组,空间复杂度是,远低于堆排序的。对于庞大的数据量,应该优先选择堆排序。

    如果使用heapq内置模块,寻找数组中的第K个最大元素就是一行代码,heapq中的nlargest接口封装好了,返回的是一个数组,需要切片取值。

    import heapq

    class Solution:

    def findKthLargest(self, nums: List[int], k:int) ->int:

    returnheapq.nlargest(k,nums)[-1]

    当然,一般都是手写堆排序,寻找数组中的第K个最大元素建立最小堆,寻找数组中的第K个最小元素建立最大堆,

    思路:「取nums前K个元素建立大小为K的最小堆,后面就是维护一个容量为k的小顶堆,堆中的k个节点代表着当前最大的k个元素,而堆顶显然是这k个元素中的最小值。」

    因此只要遍历整个数组,当二叉堆大小等于K后,当遇见大于堆顶数值的元素时弹出堆顶,并压入该元素,持续维护最大的K个元素。遍历结束后,堆顶元素即为第K个最大元素。时间复杂度。

    class Solution:

    def findKthLargest(self, nums: List[int], k:int) ->int:

    heapsize=len(nums)

    def maxheap(a,i,length):

    l=2*i+1

    r=2*i+2

    large=i

    if la[large]:

    large=l

    if ra[large]:

    large=r

    if large!=i:

    a[large],a[i]=a[i],a[large]

    maxheap(a,large,length)

    def buildheap(a,length):

    foriinrange(heapsize//2,-1,-1):

    maxheap(a,i,length)

    buildheap(nums,heapsize)

    foriinrange(heapsize-1,heapsize-k,-1):

    nums[0],nums[i]=nums[i],nums[0]

    heapsize-=1

    maxheap(nums,0,heapsize)

    returnnums[0]

    相反如果是求前k个最小,那么就用最大堆,因此面对TopK问题,最完美的解法是堆排序。因此,只有你看到数组的第K个……,马上就是想到堆排序。

    如果在数据规模小、对时间复杂度、空间复杂度要求不高的时候,真没必要上 “高大上” 的算法,写一个快排就很完美了。

    TopK问题就像搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的Top10搜索关键词,啥啥惹事就出来了。

    本文已收录 GitHub https://github.com/MaoliRUNsen/runsenlearnpy100

    【编辑推荐】

    【责任编辑:姜华 TEL:(010)68476606】

    点赞 0

    展开全文
  • TopK问题就像搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的Top10搜索关键词,啥啥惹事就出来了。

    @Author:Runsen

    上次介绍了堆排序,这次介绍堆排序常见的应用场景TopK问题和。

    利用堆求TopK问题

    TopK问题是一个堆排序典型的应用场景。

    题目是这样的:假设,我们想在大量的数据,如 100 亿个整型数据中,找到值最大的 K 个元素,K 小于 10000。对此,你会怎么做呢?

    对标的是Leetcode第215题:数组中的第K个最大元素。

    具体链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    示例 1:
    
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
    示例 2:
    
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
    

    经典的TopK问题还有:最大(小) K 个数、前 K 个高频元素、第 K 个最大(小)元素

    对此TopK问题本质上是一个排序问题,排序算法一共有十个,这个还有很多排序算法没有介绍过。

    至于为什么TopK问题最佳的答案是堆排序?其实在空间和时间的复杂度来考量,虽说快排是最好的排序算法,但是对于100亿个元素从大到小排序,然后输出前 K 个元素值。

    可是&#x

    展开全文
  • 堆排序--TOP-K问题解决及复杂度分析

    千次阅读 2022-04-09 17:00:52
    堆排序算法实现,TOP-K问题解决代码及复杂度分析。
  • 堆排序TopK问题

    多人点赞 热门讨论 2021-11-30 11:09:21
    堆排序 』的应用很多,其本质其实是运用的『 二叉树 』的顺序结构,同时堆排序也是一种复杂度logN的很快的排序算法,典型的就是能够解决TopK问题 』。并且在数据结构中『 优先级队列 』的本质也是堆。 一、...
  • [数据结构]堆的经典——TopK问题堆排序

    千次阅读 多人点赞 2022-03-27 15:43:35
    详细讲解堆中经典的TopK问题堆排序以及实现源码
  • 堆排序实现及top-K问题

    千次阅读 2022-04-10 17:33:31
    对于一个任意的数组实现堆排序 方法一:向上调整法 将这个数组看成一个堆,从第二个元素开始进行向上调整直至最后。 即先将前两个元素看成堆,进行向上调整 后再将前三个元素看成一个堆,再进行向上...
  • 最小堆解决 Top K 问题

    2018-10-14 00:00:53
    虽然这能解决问题,但效率不高,因为我们只需要部分有序,它却对整体进行了排序。最小是解决Top K 问题的一个好的方法(如果我们需要选出K个最小的数,用的是最大)。 Top K 实现步骤 最小也叫小根,...
  • 堆排序 + Top K 问题

    2022-03-15 20:42:40
    [C++][Leetcode][TopK]前K大问题+前K高频(堆+map)_D.Guan的博客-CSDN博客 在大规模数据的时候,快速排序只会线性增长,而堆排序增加幅度很大,会远远大于线性。 堆排序指针寻址会耗费很多...
  • 排序——堆排序TopK

    千次阅读 2019-04-02 10:56:54
    堆排序TopK问题,面试中还是经常问的,索性也整理一下。下面是徒手写的,供参考. 堆排序 public void heapSort(int[] array) { // 先构造一个大顶堆 int N = array.length - 1; for (int i = (N - 1) / 2; i ...
  • Top K问题——堆排序

    2019-02-20 11:04:27
    题解:Top k问题即在大量数据(n&gt;&gt;100000)中查找前k个最大的数据。 思路:排序是不可取的,因为大量数据排序耗时太大,且空间复杂度也很大,一般利用数据结构的最小(最小即父节点的值小于等于...
  • 源代码里面解决了:建堆(给一个数组建堆),堆的各项操作,堆排序TopK问题。PS:代码里面有详细的解释哈。main函数里面test1里面是建堆的各项操作的测试及堆排序的测试。 test2里面是给一个数组然后建堆的测试哈。
  • 堆排序以及TopK问题

    千次阅读 2018-08-27 16:06:47
    堆排序 利用数组来实现堆,堆分为小顶堆和大顶堆 小顶堆:父亲节点的值小于左右孩子节点 大顶堆:父亲节点的值大于左右孩子节点  如果是对数组从小到大排序 (1)为数组构建一个初始大顶堆,则数组的第一个...
  • Top K问题 ----堆排序

    2018-08-18 20:24:00
    问题大致描述: 在海量数据中选出前K个最大的数据 输入:  第一行:输入K,表示要求选出的K个最大的数  第二行:输入一个数 ...思路:因为要在海量的数据中选出K个数,所以可以利用堆排序,建立小根堆, 在用...
  • 题目:分析求解topk(big)问题堆排序 和 快速排序 的使用场景 快速排序求解 &nbsp; &nbsp; &nbsp; &nbsp;这种算法利用了快速排序的主要思想:每次调用快速排序的partition函数后将会得出一个数n...
  • 一:建 第一种情况:时间复杂度O(logn) 若左右子树恰好都是小,如何建小呢? 算法:向下调整算法 1. 选出孩子中小的那一个 a)小的孩子跟父亲相比,比父亲小则与父亲交换,并把原来孩子的位置当成父亲...
  • 一、基础知识 1.1 什么是最大(小) 最大,最小类似,以下以最小为例进行讲解。...1.3 什么是TOP K问题 Top K指的是从n(很大)个数据中,选取最大(小)的k个数据。例如学校要从全校学...
  • 3.2在原本数组上建3.2.1向上调整-插入数据3.2.2 向下调整-删除数据3.2.3比较时间复杂度3.3代码示例4.TopK问题4.1问题说明4.2如何求解?4.3测试代码结语 前言 在上一篇数据结构博客中,我带大家一起学习了树以及...
  • 堆排和TopK问题堆排序:基本思想:代码实现:TopK堆排序: 基本思想: 当我们要实现一个堆排序的时候,首先考虑是建大堆还是小堆,如果建小堆,根节点一定是最小的,而根节点的子节点不一定是次小的(如下图一...
  • 【数据结构】用堆解决Top-K问题

    多人点赞 热门讨论 2021-11-12 15:14:46
    生活中我们每每都会遇到Top-K问题,例如搜索附近前几的的奶茶店,频率前几的搜索字符串等等 如果只是数据比较少的,我们可以排序找到前几的数据 但是实际应用中我们时常都会面对海量的数据,大到内存无法全部加载...
  • 堆与堆排序topK问题

    千次阅读 2016-04-11 20:26:06
    堆与堆排序topK问题
  • 【数据结构入门】堆的应用:TopK & 堆排序

    千次阅读 多人点赞 2022-02-28 19:42:00
    文章目录一、Top-k问题1.1 解法一:暴力排序1.2 解法二:建N个数的堆1.3 解法三:建K个数的堆(最优解法)二、堆排序 一、Top-k问题 Top-k问题:在 N 个数中,找出前 K 个(最大/最小)的元素,一般情况下数据量 N ...
  • 1)排序 堆排序 选择排序 既可以找到最大的放在最后 也可以找到最小的方最前 但是,堆排序不能找最小的放在最前 因为把最小数放在最前,会破坏掉堆的原来的顺序,除非重新建堆 1, 2,9,16,7,15,18,45,...
  • 一、什么是 得满足两个特性:1、首先得是一个完全二叉树 2、每个节点比其孩子节点都大(小),则其是大(小)是将其元素存储在一维数组中的。 二、的创建 1、首先了解向下调整算法: 向下调整...
  • //元素数组建 //通过向上调整法建立 void HeapSort(int *a,int size) { assert(a); assert(size==1); for(size_t j=1;j<size;j++) { AdjustUp(a,j); } } //使用向下调整建 //向...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,341
精华内容 13,736
关键字:

堆排序解决topk问题