摘要

堆可以分为大顶堆和小顶堆,是根据节点与子节点的比较来界定。文章中可以使用数组来存放元素,并处理节点与子节点的比较和交换,就是利用了二叉树的基础性质,看完文章相当于再次温习了二叉树的基础性质。

堆可以分为大顶堆和小顶堆,大顶堆的定义就是每个节点的值都大于或等于其左右子节点的值。小顶堆和大顶堆相反,即每个节点的值都小于或等于其左右子节点的值。接下来的说明以大顶堆为例。

根据大顶堆的定义可以梳理出这几点特性:

1、 根节点的值是最大的;
2、 节点的左右子节点没有左子节点值必须小于右子节点值,反之也是没有限制;
3、 节点、它的左子节点、它的右子节点这三个节点中,节点的值是最大的;

接下来,咱就用数组来实现大顶堆的数据结构。为什么要用数组而不是二叉树来实现?带着问题,继续往下看,后面给出答案。

首先创建一个大顶堆的类结构,并定义数组、数量等属性

public class BinaryHeap<E> {
   
     
		private E[] elements;
		private int size;
}

假设将elements 数组里 index 索引中的元素放到合适的位置,这时就要考虑两点:

1、 index索引位置在叶子节点;
2、 index索引位置在非叶子节点;

如果是情况1,那就可以不做处理,因为依据特性2来看,子节点之间没有比较元素的要求,凡是叶子节点,都是子节点,所以叶子节点可以不用处理,等着它的父节点来主动比较。

如果是情况2,那么就需要和它的左右子节点比较,然后和最大值的节点交换,在编写逻辑之前,首先要确定以下几点(假定节点的索引为 index,数组中元素的数量为 size):

  • 非叶子节点的数量 half = size >>` 1(half = size / 1);
  • 节点的左子节点索引 leftIndex = (index `<< 1) + 1;
  • 节点的右子节点索引 rightIndex = leftIndex + 1;

位运算符示例:

x<< 1: x *2

x>> 1: x / 2

上面这3 点都是二叉树的基本特性,可以看第六期再温习一下,下面就可以编写防治 index 索引的节点的代码:

private void siftDown(int index) {
   
     
  E element = elements[index];

  int half = size >> 1; // 取出非叶子节点
  // 第一个叶子结点的索引 == 非叶子节点的数量
  // 必须保证 index 是非叶子节点
  while (index < half) {
   
     
    // index 的节点有2种情况
    // 1、只有左子节点
    // 2、同时有左右子节点

    // 默认左子节点跟它进行比较
    int childIndex = (index << 1) + 1;
    E child = elements[childIndex];
    // 右子节点
    int rightIndex = childIndex + 1;
    // 保证右子节点存在(rightIndex < size),并比较左右子节点
    if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
   
     
      child = elements[ childIndex = rightIndex];
    }
    if (compare(child, element) < 0) break;

    // 将子节点存放到index位置
    elements[index] = child;
    // 重新设置 index,继续判断
    index = childIndex;
  }
  elements[index] = element;
}

siftDown 方法的实现逻辑,可以发现是从 index 往下过滤,寻找合适的位置,那么有没有从 index 往上过滤呢?上代码:

private void siftUp(int index) {
   
     
  E e = elements[index];
  while (index > 0) {
   
     
    // 得到 index 位置节点的父节点
    int pIndex = (index - 1) >> 1;
    E p = elements[pIndex];
    // 节点小于或等于它的父节点时,结束
    if (compare(e, p) <= 0) break;
		// 交换节点元素,父节点设置为 index 节点再进行判断
    elements[index] = p;
    index = pIndex;
  }
  elements[index] = e;
}

(index - 1) >> 1 就是获取父节点索引代码,也是二叉树的基本性质。

当解决将 index 索引节点放在合适位置的核心问题之后,就可以处理后面这几个需求了。

比如,当需要批量添加元素,即直接将一个数组处理成大顶堆时(假设元素已经放入 elements 中 ):

// 批量建堆
private void heapify() {
   
     
  // 自下而上的下滤,只需要处理非叶子节点即可
  for (int i = (size >> 1) - 1; i >= 0; i--) {
   
     
    siftDown(i);
  }
}

如果使用 siftUp 函数来实现批量建堆,就需要从头遍历到最后的位置:

// 批量建堆
private void heapify() {
   
     
  // 自上而下的上滤
  for (int i = 0; i < size; i++) {
   
     
    siftUp(i);
  }
}

总结

  • 大顶堆就是每个节点都大于它的左右子节点,小顶堆刚相反;
  • 非叶子节点的数量 half = size >>` 1(half = size / 1);
  • siftDown 来批量建堆时,可以减少一半的遍历次数;