Java PriorityQueue(堆)插入n个元素的时间复杂度? [英] Time Complexity of Java PriorityQueue (heap) insertion of n elements?

问题描述

我想知道Java PriorityQueue.Add()对于n元素的时间复杂度是多少.

I would like to know what the time complexity of Java PriorityQueue.Add() is for n elements.

我知道插入单个元素可能会导致更坏的情况，但是我不清楚插入n个元素的集合的时间复杂度是多少?

I understand that potential worse case insertion a single element is O(log(n)), but it is not clear to me what the time complexity is for inserting a collection of n elements?

我已经从各种来源(没有证据)中断言，建立n元素的优先级队列堆的时间是O(n)，并且还看到了断言是O(nlog(n))的时间，这使得感觉到给定的插入是O(log(n))，乘以n倍实际上等于O(nlog(n))

I've seen claims from various sources (with no proofs) that the time to build a priority queue heap of n elements it is O(n), and have also seen claims that it is O(nlog(n)), which makes sense given insertion is O(log(n)), which multiplied n times would indeed equal O(nlog(n))

注意:我只对更坏的情况感兴趣，不会摊销.

Note: I'm only interested in worse case, not amortized.

此问题假定存在一种逻辑方法来描述用n元素填充数据结构(堆)的行为，这与简单地单独考虑n x log(n)插入不同.

This question assumes there is a logical way to describe the act of populating a data structure (heap) with n elements, that is different than simply considering n x log(n) insertions individually.

我对输入没有任何假设(例如输入值集的边界或部分排序的输入).

I'm making no assumptions regarding the input (such as a bounds on the set of input values, or a partially ordered input).

推荐答案

通常情况下为 O(N log N).对于已经订购了输入的特殊情况，存在 O(N)算法，但是java.util.PriorityQueue中未提供此算法.

It is O(N log N) in the general case. An O(N) algorithm exists for the special case where the input is already ordered, but this isn't provided in java.util.PriorityQueue.

这篇关于Java PriorityQueue(堆)插入n个元素的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！