堆(heap)数据结构的应用

2021年3月12日12:56:35 发表评论 443 次浏览

数据结构通常由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

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: