关于堆

关于堆

堆本质上是用数组实现的二叉树。

大根堆：一棵完全二叉树，满足任一节点都比其子节点大；用于升序排列

小根堆：一棵完全二叉树，满足任一节点都比其他子节点小；用于降序排列

如何用数组实现堆？

节点在数组中的位置index 和它的父节点以及子节点的索引之间有一个映射关系。

parent(i) = floor((i - 1)/2)             //floor函数表示向下取整
left(i)   = 2i + 1
right(i)  = 2i + 2

[ 10, 7, 2, 5, 1 ]

Node	Array index (i)	Parent index	Left child	Right child
10	0	-1	1	2
7	1	0	3	4
2	2	0	5	6
5	3	1	7	8
1	4	1	9	10

使用数组索引代替指针，节约了空间，但是需要进行更多的计算。（这就是交易）