二叉堆
什么是二叉堆
二叉堆本质上是一种完全二叉树, 它又分为两种
- 最大堆: 任意一个父节点的值都大于等于它的左右子节点的值
- 最小堆: 任意一个父节点的值都小于等于它的左右子节点的值
二叉堆的根节点叫做对顶。
最大堆和最小堆的特点,决定了在最大堆的堆顶是整个堆中最大的元素,最小堆的堆顶是整个堆中最小的元素
二叉堆的自我调整
对于一个二叉堆,有如下几种操作
- 插入节点
- 删除节点
- 构建二叉堆
1.插入节点(以最小堆为例)
插入的位置是完全二叉树的最后一个节点位置,例如我们插入的值为 0
这时候,我们让节点0和它的父节点做比较,因为0小于5,所以让新节点上浮,与父节点交换位置
继续用0和3作比较,0小于3,所有0和3交换位置,让新节点继续上浮
继续比较,最终让新节点0上浮到了堆顶位置。
2.删除节点
二叉堆节点的删除与插入过程刚好相反,所删除的是处于堆顶的节点,比如我们删除最小堆的堆顶节点1。
这时候,为了位置完全二叉树的结构,我们把堆的最后一个节点10补到堆顶的位置
接下来我们让移动到堆顶的节点10和它的左右孩子节点进行比较,如果左后孩子节点中最小的一个比节点10小,则交换两个元素的位置,即元素10 下沉。
继续让节点10和它的左右孩子进行比较,左右孩子中最小的节点是7,且10大于7,则让10与7进行交换,即10下沉。
这样,二叉堆重新得到了调整。
3.构建二叉堆
构建二叉堆,就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有的子节点一次下沉。
我们举一个无序完全二叉树的例子:
首先,从最后一个非叶子节点开始,即10,如果节点10大于它左右孩子节点中最小的一个,则节点10下沉。
之后,轮到节点3,显然,依照上面的逻辑,3会与2进行交换。
接下来是1节点,1节点并不大于它左右孩子节点中最小的一个,所有不用交换。
接下来是7节点,7 大于1,则7节点下沉。
7节点还是大于它左右孩子节点,继续下沉,与5交换。
这样一来,一颗无序的完全二叉树就构建成了一个最小堆。
堆的代码实现
说明: 二叉堆虽然一个完全二叉树,但是它的存储方式并不链式存储,而是顺序存储,即二叉堆的所有节点都存储在数组当中。
数组中,在没有左右指针的情况下,如何定位到一个父节点的左孩子和右孩子呢?
像图中那样,我们可以依靠数组下标来计算。
假设父节点的下标是parent,那么它的左孩子下标就是 2*parent+1;它的右孩子下标就是 2*parent+2 。
代码实现
/**
* 上浮调整
* @param array 待调整的堆
*/
public static void upAdjust(int [] array) {
int childIndex = array.length - 1;
int parentIndex = (childIndex - 1) / 2;
// temp保存插入的叶子节点值,用于最后的赋值
int temp = array[childIndex];
while(childIndex > 0 && temp < array[parentIndex]){
//无需真正交换,单向赋值即可
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex-1) / 2;
}
array[childIndex] = temp;
}
/**
* 下沉调整
* @param array 待调整的堆
* @param parentIndex 要下沉的父节点
* @param parentIndex 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex, int length) {
// temp保存父节点值,用于最后的赋值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有右孩子,且右孩子小于左孩子的值,则定位到右孩子
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
// 如果父节点小于任何一个孩子的值,直接跳出
if (temp <= array[childIndex])
break;
//无需真正交换,单向赋值即可
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/**
* 构建堆
* @param array 待调整的堆
*/
public static void buildHeap(int[] array) {
// 从最后一个非叶子节点开始,依次下沉调整
for (int i = array.length / 2; i >= 0; i--) {
downAdjust(array, i, array,length - 1);
}
}
public static void main(String[] args) {
int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
upAdjust(array);
System.out.println(Arrays.toString(array));
array = new int[] {7,1,3,10,5,2,8,9,6};
buildHeap(array);
System.out.printin(Arrays.toString(array));
}