问题描述
假设我们有n个元素的二进制堆和希望插入n多元素（不一定是另外一个后）。什么是为此所需的总时间？
Suppose we have a binary heap of n elements and wish to insert n more elements(not necessarily one after other). What would be the total time required for this?
我觉得这是THETA（N LOGN）作为一个插入需要LOGN。
I think it's theta (n logn) as one insertion takes logn.
推荐答案
假设我们给出：
- 通过标准的二叉堆实施
- 在优先级队列中的 ^ h （在数组实现）
- N 堆当前大小
- priority queue implemented by standard binary heap H (implemented on array)
- n current size of heap
我们有如下的插入属性：
- 在W（N）=最坏情况（N）=Θ（LG N）（西塔）。 - > W（N）=Ω（LG n）和W（N）= O（LG N）
- A（N）= AverageCase（N）=Θ（LG N）（西塔）。 - > W（N）=Ω（LG n）和W（N）= O（LG N）
- B（N）= BestCase（N）=Θ（1）（西塔）。 - > W（N）=Ω（1）和W（N）= O（1）
因此，对于的任何情况下的，我们有
So for every case, we have
- T（N）=Ω（1）和T（N）= O（LG N）
最坏情况是，当我们插入新的最小值，因此向上堆有出行整个分支。
WorstCase is when, we insert new minimal value, so up-heap has to travel whole branch.
BestCase是时，对于最小堆（堆以最小的顶部），我们插入大（最大的更新分支）值（所以向上堆立即停止）。
BestCase is when, for minimal-heap (heap with minimal on top) we insert BIG (biggest on updated branch) value (so up-heap stops immediately).
您已经询问了N系列的操作上已经包含n个元素的堆，它的大小将增长
You've asked about series of n operations on heap containing already n elements,it's size will grow
from n to 2*n
什么渐近就是...
what asymptotically is ...
n=Θ(n)
2*n=Θ(n)
什么简化了我们的方程式。 （我们不担心增长的 N 的，因为它的增长是恒定的因素）。
What simplifies our equations. (We don't have to worry about growth of n , as it's growth is by constant factor).
所以，我们有n个插入操作：
So, we have "for n insertions" of operation:
- 在熙（N）= X_for_n_insertions（N）
- 在无线网络（N）=Θ（N LG N）
- 在艾（N）=Θ（N LG N）
- 双（N）=Θ（N）
- Xi(n) = X_for_n_insertions(n)
- Wi(n) = Θ(n lg n)
- Ai(n) = Θ(n lg n)
- Bi(n) = Θ(n)
- 钛（N）=Ω（n）和钛（N）=为O（n LG N）
P.S。为了显示西塔Θ，欧米茄Ω符号，你需要有UTF-8安装/兼容。
P.S. For displaying Theta Θ , Omega Ω symbols, you need to have UTF-8 installed/be compatible.
这篇关于插入n个元素为二进制堆已含有n个元素的渐近时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！