二叉堆

 

二叉堆

什么是二叉堆

二叉堆本质上是一种完全二叉树, 它又分为两种

  1. 最大堆: 任意一个父节点的值都大于等于它的左右子节点的值img
  2. 最小堆: 任意一个父节点的值都小于等于它的左右子节点的值img

二叉堆的根节点叫做对顶。

最大堆和最小堆的特点,决定了在最大堆的堆顶是整个堆中最大的元素,最小堆的堆顶是整个堆中最小的元素

二叉堆的自我调整

对于一个二叉堆,有如下几种操作

  1. 插入节点
  2. 删除节点
  3. 构建二叉堆
1.插入节点(以最小堆为例)

插入的位置是完全二叉树的最后一个节点位置,例如我们插入的值为 0img

这时候,我们让节点0和它的父节点做比较,因为0小于5,所以让新节点上浮,与父节点交换位置img

继续用0和3作比较,0小于3,所有0和3交换位置,让新节点继续上浮img

继续比较,最终让新节点0上浮到了堆顶位置。img

2.删除节点

二叉堆节点的删除与插入过程刚好相反,所删除的是处于堆顶的节点,比如我们删除最小堆的堆顶节点1。img

这时候,为了位置完全二叉树的结构,我们把堆的最后一个节点10补到堆顶的位置img

接下来我们让移动到堆顶的节点10和它的左右孩子节点进行比较,如果左后孩子节点中最小的一个比节点10小,则交换两个元素的位置,即元素10 下沉。

img

继续让节点10和它的左右孩子进行比较,左右孩子中最小的节点是7,且10大于7,则让10与7进行交换,即10下沉。

img

这样,二叉堆重新得到了调整。

3.构建二叉堆

构建二叉堆,就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有的子节点一次下沉。

我们举一个无序完全二叉树的例子:

img

首先,从最后一个非叶子节点开始,即10,如果节点10大于它左右孩子节点中最小的一个,则节点10下沉。img

之后,轮到节点3,显然,依照上面的逻辑,3会与2进行交换。img

接下来是1节点,1节点并不大于它左右孩子节点中最小的一个,所有不用交换。

接下来是7节点,7 大于1,则7节点下沉。

img

7节点还是大于它左右孩子节点,继续下沉,与5交换。img

这样一来,一颗无序的完全二叉树就构建成了一个最小堆。

堆的代码实现

说明: 二叉堆虽然一个完全二叉树,但是它的存储方式并不链式存储,而是顺序存储,即二叉堆的所有节点都存储在数组当中。

img

数组中,在没有左右指针的情况下,如何定位到一个父节点的左孩子和右孩子呢?

像图中那样,我们可以依靠数组下标来计算。

假设父节点的下标是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));
}