堆
June 14, 2022
定义 #
一个特殊的二叉树结构
用数组表示时,对于数组中索引位置为 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)]
通常用来实现优先队列