几种不同类型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），详细参见《算法导论》。