June 14, 2022
data-structure

定义 #

一个特殊的二叉树结构

用数组表示时,对于数组中索引位置为 i 的元素,其对应树表示中,父节点,左右子节点的索引满足以下关系:

Parent(i) = Math.floor(i/2)

Left(i) = 2*i

Right(i) = 2*i + 1

Max heap #

最大堆

除了根节点 A[i] <= A[parent(i)]

Min heap #

最小堆

除了根节点,A[i] >= A[parent(i)]

通常用来实现优先队列

维持堆属性 #

构造最大堆 #

堆排序 #

优先队列 #