top k 问题：堆排序法
发布时间
阅读量：
阅读量
题解：Top k问题即在大量数据（n>>100000）中查找前k个最大的数据。
思路：排序并非理想的解决方案。由于处理海量数据时排序所需的时间成本过高且空间复杂度也非常大，则通常我们采用最小堆这一数据结构来进行操作。其中最小堆的特点是父节点的值小于或等于其子节点的值。
具体做法：构建一个包含K个节点的最小堆结构，并对海量数据依次进行比对操作。对于每一个待比对的数据样本，在与当前堆顶元素进行对比时若发现其数值低于当前堆顶，则将其排除在外；反之，则将该新数值替代当前堆顶元素，并对整个堆展开必要的重构以维持其最小化特性。经过上述操作后，在最终状态下剩余在小端树中的K个数据即为所筛选出的最大值集合。
时间复杂度=nlogK（堆调整时间复杂度为logK）；
推排序
转：<>
（1）思想
将待排序的元素按照大小依次放置于二叉树的位置上，在完成排序后其中每个父节点中的元素必须大于或等于其子节点中的内容。这一过程被称为堆化过程。若该堆中存储的最大值位于根节点，则称其为大顶堆；反之，则称为小顶 heap 了。基于此特性（大顶 heap 中顶端存储最大值、小顶 heap 中则最小），我们可以依次取出顶端元素并重新进行调整
还没有任何评论哟~