常用数据结构之堆

  数据结构是一种特殊的组织和存储数据的方式,使我们可以更高效的对存储的数据执行操作。以下介绍常用的数据结构中的堆结构。

堆的定义

  n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆

  • (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2) 

  堆实质上是满足如下性质的完全二叉树:

  • 树中所有非终端结点的值均不大于(或不小于)其左右孩子结点的值。

堆的类型  

  • 最小堆(min-heap):

    父结点的值小于或等于子结点的值,根将包含堆的最小值。

  • 最大堆(max-heap):

   父结点的值大于于或等于子结点的值,根将包含堆的最大值。

   下图显示了如何使用二叉树和数组表示最大堆。

常用数据结构之堆常用数据结构之堆

 

堆的应用

  • 用于实现优先级队列,因为可以根据堆属性对优先级值进行排序。
  • 用于查找给定数组中k个最小(或最大)的值
  • 用于堆排序算法

以上学习总结参考:https://www.jianshu.com/p/6b526aa481b1、https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin、https://mp.weixin.qq.com/s/rycQvasVNGcozyDiropSow。

上一篇:Commonsense Causal Reasoning between Short Texts


下一篇:周鸿祎携奇酷手机卷土重来,雷军 Are You OK ?