幾種不同類型Heap的對比

  第一種：Ordinary Heap

  我們最常用的二叉樹結構的堆，操作的時間複雜度為

  MAKE-HEAP - O（1）

  INSERT - O（lg n）

  MINIMUM - O（1）

  EXTRACT-MIN - O（lg n）

  UNION - O（n）

  DECREASE-KEY - O（lg n）

  DELETE - O（lg n）

  可以看出，除了UNION需要O（n）外，其它操作的時間複雜度都是可以接受的，而且由于實作非常簡單，在UNION操作很少的情況下，可以考慮使用這種結構的堆。

  第二種：Fibonacci Heap

  具體的結構和操作較為複雜，詳細參見《算法導論》，它的操作時間複雜度為

  MAKE-HEAP - O（1）

  INSERT - O（1）

  MINIMUM - O（1）

  EXTRACT-MIN - O（lg n）

  UNION - O（1）

  DECREASE-KEY - O（1）

  DELETE - O（lg n）

  可以看出，所有的操作均要比第一種的堆快（但要注意第二種中的複雜度是amortized，而第一種中的複雜度是worst-case），但由于實作和操作比較複雜，是以，隻有在特别要求效率的情況下，才會使用。

  第三種：Binomial Heap

  這是Mergable Heap中很重要的一種，結構和操作的複雜程度介于Ordinary Heap和Fibonacci Heap之間，詳細參見http://en.wikipedia.org/wiki/Binomial_heap，操作的時間複雜度為

  MAKE-HEAP - O（1）

  INSERT - O（lg n）

  MINIMUM - O（lg n）

  EXTRACT-MIN - O（lg n）

  UNION - O（lg n）

  DECREASE-KEY - O（lg n）

  DELETE - O（lg n）

  可以看出，UNION操作較Ordinary Heap有了提升，是以，如果在應用中有很多UNION操作，而你又不想采用太複雜的結構，可以使用這種Heap。

  第四種：van Emde Boas Trees

  這種形式的結構和操作極其複雜，應用範圍較為局限，它的資料要求是0～u的範圍内無重複的數字（當然你可以對此進行改進，使其支援重複數字），而且u需要是2的n次幂。但它的性能超過了lg n這個基于比較的堆的複雜度下限，所有操作的時間複雜度達到了O（lg lg n），詳細參見《算法導論》。