堆(heap)数据结构的应用

堆数据结构通常由Heapsort教授。 Heapsort算法的用途有限, 因为Quicksort在实践中会更好。但是, 堆数据结构本身已被大量使用。以下是除Heapsort以外的一些用途。

优先队列：可以使用Binary Heap有效地实现优先级队列, 因为它支持O(logn)时间中的insert(), delete()和extractmax(), reducingKey()操作。 Binomoial堆和Fibonacci堆是Binary堆的变体。这些变体也在O(logn)时间执行并集, 这是Binary Heap中的O(n)操作。在图算法中使用堆实现的优先级队列, 例如普里姆的算法和Dijkstra的算法.

订单统计：堆数据结构可用于有效地找到数组中第k个最小(或最大)的元素。参见方法4和6这个详细信息。

参考文献：

http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap07.htm

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。