用于对集合中的最大X数进行排序的最佳算法是什么

Question

从一组N个数(N> X)中提取X个最大数的排序列表的最佳算法是什么.使用大多数算法,我们可以O(NlogN)及时完成.但是有可能做得更好吗？例如,使用二叉树:O(NLogX)？.集合中的数字是完全随机的.

Answer 1

使用大小为X 的最小堆.

将前X个元素插入堆中.从元素X +1开始(称之为e),将其与堆m的顶部(目前为止的最小值)进行比较.请注意,此比较将在恒定时间内完成.如果e > m,则e值得进入(提取m并插入e).为集合中的每个元素执行此操作.在此过程结束时,您的堆包含X个最大数字.然后抽取-min X次将给出您期望的排序列表.

N次迭代中的每一次执行潜在的O(lgX)提取/插入操作,因此第一步是O(NlgX)时间.然后,你的最小堆中的X extract-min的成本将是简单的O(XlgX),这给了我们整体的复杂性O(NlgX).