三、完整代码和视图

在之前的文章中已经详细的讲解了二叉树、堆、堆排序。

那么关于堆还有一个比较有意思的题就是TopK问题。

详解二叉树和堆

Top-k问题在生活中是非常的常见比如游戏中某个大区某个英雄熟练度最高的前10个玩家的排名我们就要根据每个玩家对该英雄的熟练度进行排序可能有200万个玩家但我只想选出前10个要对所有人去排个序吗显然没这个必要。

再比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

解法一暴力排序

但是如果数据量非常大排序就不太可取了可能数据都不能一下子全部加载到内存中。

建一个

个数的堆C中可用优先级队列priority_queue不断的选数选出前

【思考】

个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

✨时间复杂度

然后把数据集合中剩下的元素与堆顶比较若大于堆顶则去掉堆顶再将其插入

个最大元素

如果你建的10个元素的大堆堆顶元素恰好是数据集合中最大的那个那第2大的数、第3大的数不就能找不到了。

三、完整代码和视图

(HPDatatype*)malloc(sizeof(HPDatatype)

建堆----用a中前k个元素建堆for

从倒数第一个非叶子节点开始AdjustDown(kminHeap,

j);}//

a[i];//如果比堆顶大就替换AdjustDown(kminHeap,

0);//向下调整确保为堆}}for

kminHeap[j]);}printf(\n);free(kminHeap);

}int

以下就是我对数据结构---堆排序的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对数据结构-------链式二叉树请持续关注我哦