插入n个元素为二进制堆已含有n个元素的渐近时间复杂度 [英] Asymptotic time complexity of inserting n elements to a binary heap already containing n elements

问题描述

假设我们有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个元素的渐近时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！