锐客网

  1. 首页 > 睿知 > it技术 > >

堆(heap)数据结构的应用

IT知识数据结构迭代堆排序优先队列

堆数据结构通常由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
【堆(heap)数据结构的应用】http://en.wikipedia.org/wiki/Heap_%28data_structure%29
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

    推荐阅读


    上一篇：AngularJS 动画制作详细实现代码

    下一篇：三星暑期实习研发面试经验|校园班加罗尔