优先队列时间复杂度
来源：8-7 Leetcode上优先队列相关问题
xiaocui_0001
2018-07-05
之前在看堆优先队列对于堆这样的 出队和入队的时间复杂度是 O(logn) 对于 在N个元素中选出前M个元素 是不是时间复杂度应该是Mlogn , logn是选出最小元素的复杂度 要拿出M个元素 所以是不是应该复杂度是MlogN,不知道我这样的说法对不对？
写回答
1回答
-
对于我们在这一小节的实现：
我们创建了一个最多包含M个元素的堆。在这个堆上的基本操作是O(logM)的。对于每一个元素，我们都可能要在这个堆上进行一次操作，所以时间复杂度是O(NlogM)的。
如果你一上来对数组中的所有元素组织成一个堆，这个过程是O(N)的，之后在这个巨大的堆中取前M个元素，时间复杂度是O(MlogN)的，综合这个过程，时间复杂度是：O(N + MlogN)的。
后一种方法有一个缺点，或者说是限制，就是需要在算法计算初始，就已知所有的数据。在Leetcode上这个问题中，这个条件可以满足。但是在实际中，数据很有可能是一点一点流进来的，而不是一次性给出的（比如用户的下单数据）；同时，由于N巨大，很有可能维持一个包含N个元素的堆是不现实的，而维持一个包含M个元素的堆，是很简单的。比如要实时统计单笔订单金额最高的前100个订单，前一种方法只需要维护一个包含100个元素的堆，而后一种方法需要维护一个包含订单总量那么多元素的堆，而订单总量可能是一个天文数字：）
4122021-01-05
相似问题
关于testQueue时间复杂度
回答 1
关于使用二分搜素树实现优先队列
回答 1