為什麼建立一個二叉堆的時間為O(N)而不是O(Nlog(N))?

RT，今天被問到這個問題，我太笨想不明白了，請問各位大佬。

我的想法如下：

由上自下，第k層有2**(k-1)個元素，同時插入第k層元素時，需要比較(k-1)次，最後算出來結果就是O(Nlog(N))

然後csdn上有一個帖子，我沒看懂。。。請各位大佬指教

構建二叉堆時間複雜度的證明 - CSDN博客

一個小時後更新：

翻了翻《數據結構與演算法分析——C++語言描述》，已經解決，建立二叉堆的時候，不是以插入建立的，而是自下而上浮上去的，每次都只和上層比較。。。。。。

---

雖然已經解決了還是簡述一下：

如果用普通插入的方式，則總的時間複雜度為

證明方式通過將求和放縮到積分進行，ln x的積分是 x ln x - x，再利用

這樣求和就可以放縮到兩個積分上

顯然階就是O(nlogn)了

而標準的構造方式從後往前進行，越是底層的節點需要的步驟反而越少，因為底層節點很多而上層節點少，於是節約了時間，總的時間複雜度為

證明方式仍然是放縮到積分，跟上面一樣的，不再贅述

證明求和式的階的最簡便的方法之一就是放縮到積分，對於單調函數非常有效。除此以外，錯位相加（或者叫做Abel求和公式）也是常用的方法。

補充一下，準確來說前面求和當中的log k應該是要向下取整的，但是因為每個取整的誤差不超過1，累積不超過O(n)，而這裡的複雜度總和肯定是超過O(n)的，所以這部分誤差不會影響最後結果，如果是考試題的話，最好改用：

當然結果是沒有區別的。

---

構建堆的過程其實和錦標賽是一樣的：

數一下非葉子節點個數就是n-1個。

---

為什麼會邀請我回答這個問題（；￣ェ￣）

我演算法學的像屎一樣……

不過題目中說已經解決了，但我還是給你提供一點微不足道的幫助吧_(′?`」 ∠)_

我印象中『演算法藝術與信息學競賽』上面有一個關於這個問題的證明。

鏈接：https://pan.baidu.com/s/1o7RTT2a 密碼：gY72

諾，這是pdf （這本書寫的很好

---

直接按照插入的方法建堆當然是nlogn的……

但是如果使用隊列建堆……用左偏樹來搞……複雜度就是n的……

---

這是小學知識

題主需要回小學重造

---

推薦閱讀：