堆-二叉堆

堆(Heap)是一种特殊的树状数据结构

堆有两种类型,满足其中一种的就可以成为堆:

1.大顶堆(Max-Heap) - 父节点总是比左右两个子节点大

2.小顶堆(Min-Heap) - 父节点总是比左右两个子节点小



堆的应用:

堆排序 - 排序基本排序好的数组更佳

优先级队列

比如 合并有序小文件、高性能定时器

求 Top n 问题

利用堆求动态数据的中位数

当然应用之前,最好和散列表、红黑树做对比,不同场景可能效率和空间占用会不同


二叉堆(Binary Heap)

二叉堆其实就是二叉树满足以下性质:

1.树必须为完全二叉树

2.必须满足大顶堆或是小顶堆

为啥要满足完全二叉树性质,因为这样就可以用数组来表示

arr[(i-1)/2]     表示i的父节点

arr[(2*i)+1]     表示i的左子节点

arr[(2*i)+2]     表示i的右子节点

下面是一张数组与树的对应图


各种操作细节参考:wiki-二叉堆

上一篇: 散列表
下一篇: 二项堆
作者邮箱: 203328517@qq.com