chapter_heap/top_k/

[giscus[bot]]

chapter_heap/top_k/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_heap/top_k/

[yuqiaoqiao]

第一次知道还有这么玩的，有点意思

[yuyu990116]

heapq.heappush(heap, nums[i])，这一步push之后不需要heapify吗

[krahets]

Hi 不需要哦，heappush() 入堆操作已经包含了堆化，heapify() 通常用于堆化输入列表的所有元素。

[zhuasdfg]

建长度为k的小顶堆实现top-K实在是泰裤辣

[marrblue]

优雅

[FlashSpiders]

// 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.peek()) {
heap.poll();
heap.add(nums[i]); // 求教，这里为什么是add不是用push()或者offer()呀，add的话也能加到堆顶吗
}

[krahets]

Hi 在 Java 的 PriorityQueue 中，add() 实际上是在调用 offer() ，两者的表现是一致的。你会发现 Java 的常用数据结构基本没有用 push() 的，都是 add()

[lyl625760]

还是offer(e)更好一些， add更多和remove配合， offer更多和poll配合

[LyntNy4n]

建议解释一下为什么前k大的元素需要小根堆而不是大根堆 这里是个大坑

[krahets]

因为如果使用大根堆，我们每轮只能替换最大元素；而使用小根堆，我们每轮替换的是“第 K 大的元素”。

[maidao-yang]

因为需要剔除最小的前n-k个数，最小堆顶部的元素就是最小的元素。当n个数中最小的n-k个数被从堆中删除后，剩下的就是最大的k个数，而最小堆顶部就是最大的k个数中最小的，也就是我们要的结果。

[primexiao]

估计想问的是，使用大顶堆，先入 n-k个元素，然后剩余的k个元素每次跟堆顶对比得到较大的一个，这样操作 k 次是不是也能得到 Top-k ？

[lyl625760]

太棒了

1. 利用上节内容，建堆代码可以优化下， 复杂度更低。

// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
    heap.offer(nums[i]);
}

可以优化成

Queue<Integer> heap = new PriorityQueue<Integer>(Arrays.stream(nums).collect(Collectors.toList()));        

2. 可以稍微提下 topk的其他解法，如快速排序

[krahets]

谢谢建议！

[palp1tate]

遍历和排序提供代码：

遍历

Python：

def findKthLargest(nums, k):
    result = []
    for i in range(k):
        max_num = max(nums)
        result.append(max_num)
        nums.remove(max_num)
    return result

Go：

func findKthLargest(nums []int, k int) []int {
	result := make([]int, k)
	for i := 0; i < k; i++ {
		max := nums[0]
		index := 0
		for i, num := range nums {
			if num > max {
				max = num
				index = i
			}
		}
		result[i] = max
		nums = append(nums[:index], nums[index+1:]...)
	}
	return result
}

排序

Python：

def findKthLargest(nums, k):
    nums.sort(reverse=True)
    return nums[:k]

Go：

func findKthLargest(nums []int, k int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	return nums[:k]
}

//或者
func findKthLargest(nums []int, k int) []int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	return nums[:k]
}

[5710xIa]

小顶堆是不是相当于会自动排序的数组，会把最小的数排到堆顶？不过如果K较大时，排数的过程会不会很耗时？

[krahets]

是的，由于 $k \leq n$ ，最差情况下时间复杂度为 $O(n \log n)$ 。这种情况实际上就是堆排序，在排序章节有讲

[T-1760]

想请教一下，为什么 JS / TS 与 其他编程语言处理方式不同呢？

JS / TS 中是采用 ： 先对 nums 列表j进行遍历为相反数，再通过 new MaxHeap() .从而实现初始化为 minHeap 小顶堆。 导致判断逻辑也与其他编程语言不同 cur[i] < heap.peek()

那 为什么不一开始就使用 new MinHeap（），这样还节省了之前的列表遍历置反，后续又要置反输出最终结果，

[krahets]

Hi，因为这个 MaxHeap 是我们自己实现的。MinHeap 没有实现，因此需要用 MaxHeap 来模拟 MinHeap 的行为，具体做法就是将元素取反，这样做之后比较关系也完全镜像了

[T-1760]

嗯嗯，明白，谢谢

[CuiOrange]

请问代码实现部分的C语言为什么显示的是[class]{}-[func]{topKHeap}？是还没有上传代码吗？

[krahets]

是的，这部分 C 代码还待 PR 贡献

[Bbbbqsh]

大佬，想请教一下实现部分的python部分跟“把nums取负转成小顶堆，然后取k次堆顶元素，再取反”相比，哪个速度会更快呢？

def top_k_heap(nums: list[int], k: int) -> list[int]:
    l = []
    nums = [-i for i in nums]
    heapq.heapify(nums)
    for _ in range(k):
        l.append(heapq.heappop(nums) * -1)
    return l

[krahets]

先分析一下时间复杂度：

• 方法一：文中代码的时间复杂度是 $O(n \log k)$ 。
• 方法二：这段代码的时间复杂度是 $O(k \log n + n)$ ，其中复制列表 $O(n)$ ，建堆 $O(n)$ ，出堆 $O(k \log n)$ 。

最简单情况：当 $k = n$ 时，$n \log k < n \log k + n$ ，方法一稍快。
随着 $k$ 变小，从复杂度的角度估计就比较困难了，可能无法反映真实情况，实际性能要看具体的编程语言实现。

[Bbbbqsh]

明白了，感谢大佬 : )

[480284856]

上述算法应该可以直接用大顶堆做吧，省去了复制列表的 $O(n)$ 时间：
使用全部数据直接初始化一个大顶堆，时间复杂度为 $O(n)$;
从上述大顶堆中选取 $k$ 个元素，时间复杂度为 $O(k\ log\ n) $

[wenjianmin]

是不是我理解有问题？如果第k+1个元素很大的话，是不是有问题？比如[100,1,2,3,4,5]，查找Top-3时，后面的元素都不会入堆

[wenjianmin]

描述有问题，应该说第一个堆顶元素很大时。

[Bbbbqsh]

heap[0]指的是堆顶元素，也就是[100, 1, 2]中的最小值1，而不是100

[wenjianmin]

是的，看了一下初始化的时候有进行堆化

[bnufw]

heapq 模块 中也提供了一样的nlargest方法

[bnufw]

我想问一下，这里的heap=[]，并没有将heap转化为堆，即heapq.heapify(heap)。虽然程序运行是没有错误的，但我还想知道为什么可以这样做？

[bnufw]

嗷嗷，堆就是用列表来表现的

[bnufw]

为什么是n轮出堆，不应该是n-k次么

[krahets]

你是对的～文中想表达的是“入堆+出堆”操作是在 n 轮循环中完成的，呈线性关系

[HangSeven]

注意： 元素入堆 这里应该指的是单个元素入堆的时间复杂度为O(log n），对于将n个元素入堆的总体平均时间复杂度前文也提到为O(nlog n）， 只不多通过建堆的操作优化可以将时间复杂度降低到O(n)
注意：元素入堆 这里指的是单个元素入堆的时间复杂度为O(log n), 对于遍历数组入堆的总体平均时间复杂度是O(n log n)， 只是通过遍历堆化的建堆操作的时间复杂度为0(n).

[acmu]

leetcode 原题：215. 数组中的第K个最大元素

[MoCHEN-WHU]

若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
if nums[i] > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, nums[i])
实际如果进一步追求性能，这里能否进行优化，将pop与push操作融合，即直接将当前元素替换堆顶元素，然后从堆顶向下堆化，这样可以省去一个堆化操作

[krahets]

确实，实际上有类似的操作 heapq.heappushpop() （不过执行顺序相反），效率会比分开执行高一些

[a2635814919]

@krahets 老师，我看heappushpop()方法是先入堆再弹出最小的，那是否可以初始化一个k+1大小的小顶堆，存入k个元素之和不用比较，直接执行heappushpop()方法，效率是否会高一点，还有更符合先出堆后入堆操作的heapreplace()需要进行判断。python学的不精不是很确定

[a2635814919]

想询问一下8.3 Top-k问题中方法三为什么C++的函数传入的是个引用，这边对原来的数组没有进行修改，是出于效率问题还是出于习惯传入了一个引用

[krahets]

这个要根据具体情况分析。如果函数不会修改输入数据，那么一般传入引用就好。

[CcYcC8]

想问下C#的8.3.3示例代码，是忘记大顶堆取反了吗？没有很理解小顶堆怎么构造的
for (int i = 0; i < k; i++) {
heap.Enqueue(nums[i], nums[i]);
}

[hpstory]

Hi @CcYcC8 ，C#的优先队列默认就是小顶堆

[upseem]

总结：
1、小顶堆找最大K个元素：维护一个大小为K的小顶堆，堆顶元素是当前K个元素中最小的。当遇到比堆顶元素大的新元素时，替换堆顶元素并重新调整堆。
2、大顶堆找最小K个元素：维护一个大小为K的大顶堆，堆顶元素是当前K个元素中最大的。当遇到比堆顶元素小的新元素时，替换堆顶元素并重新调整堆。

[owenwu95]

C語言示例中的int *getMinHeap好像重複了

[Than-Sing]

NOTE：用heap.heapify和heap.heappushpop应该能提高一点效率

[Asce-ops]

将数组的前 k 个元素入堆的时候可以考虑改用自下而上的堆化，时间复杂度为O(log k)；之后最多进行 n - k 轮出堆和 n - k 轮入堆，所以时间复杂度最多为O(log k + 2(n - k) · log k)

[daichang01]

top-k完整实现#include
#include
#include

using namespace std;

vector top_k(vector& nums, int k) {
priority_queue<int, vector, greater> min_Heap;
for (int i = 0; i < k ;i++) {
min_Heap.push(nums[i]);
}
for (int i = k; i < nums.size(); i++) {
int top = min_Heap.top();
if (nums[i] > top) {
min_Heap.pop();
min_Heap.push(nums[i]);
}
}
vector res;
while (!min_Heap.empty()) {
res.push_back(min_Heap.top());
min_Heap.pop();
}
return res;
}

int main() {
cout << "input n and k, requeire k < n:" << endl;
int n , k;
cin >> n >> k;
int num;
vector nums(n);
cout << "input n ints:" << endl;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
vector res = top_k(nums, k);
cout << "top-k:";
for (int i : res) {
cout << i << " ";
}
return 0;
}

[tstanon]

top_k最大k个元素的C语言版本代码

void top_k(float *arr, int size, float *res, int k) {
    if (k <= 0 || k > size) return;
    float *heap = (float *)malloc(sizeof(float) * k); int heap_size = 0;
    for (int i = 0; i < k; i++){ pushHeap(heap, &heap_size, arr[i]); } //  // 初始化堆，放入前 k 个元素
    for (int i = k; i < size; i++){ if (arr[i] > heap[0]) { float tmp; popHeap(heap, &heap_size, &tmp); pushHeap(heap, &heap_size, arr[i]); } } // 处理剩余的元素
    for (int i = 0; i < k; i++) { popHeap(heap, &heap_size, &res[k - 1 - i]); } // 将堆中的元素按降序输出到 res 数组
    freeHeap(&heap);
}

[Ares-bit]

这C写的topk肯定有问题啊，怎么能初始化一个长度为0的heap然后往里push呢，这肯定段错误啊

[stazhenghaofu]

只加了3个啊，，全部比较完，最小的肯定在上面啊