数据结构之堆
思考 假如需要设计一种数据结构，用来存放整数，要求提供3个接口：
- 添加元素
- 获取最大值
- 删除最大值 如果使用动态数组、双向链表和二叉树实现这个数据结构对应的时间复杂度如下表所示：
有没有更优的数据结构？使用堆，可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。
堆的介绍 堆（Heap）也是一种树状的数据结构（不要跟java内存模型中的“堆空间”混淆），常见的堆实现有：
- 二叉堆（Binary Heap，完全二叉堆）
- 多叉堆（D-heap、D-ary Heap）
- 索引堆（Index Heap）
- 二项堆（Binomial Heap）
- 斐波那契堆（Fibonacci Heap）
- 左倾堆（Leftist Heap，左式堆）
- 斜堆（Skew Heap） 本文中主要介绍的是二叉堆。
堆的性质：任意节点的值总是 ≥（ ≤ ）子节点的值
- 如果任意节点的值总是 ≥ 子节点的值，称为：最大堆、大根堆、大顶堆
- 如果任意节点的值总是 ≤ 子节点的值，称为：最小堆、小根堆、小顶堆 由此可见，堆中的元素必须具备可比较性（跟二叉搜索树一样）。
二叉堆（Binary Heap） 二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆。
鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可。
数组中索引i的规律（n是元素数量）：
- 如果 i = 0 ，它是根节点
- 如果 i > 0 ，它的父节点的索引为 floor( (i – 1) / 2 )
- 如果 2i + 1 ≤ n – 1，它的左子节点的索引为 2i + 1
- 如果 2i + 1 > n – 1 ，它无左子节点
- 如果 2i + 2 ≤ n – 1 ，它的右子节点的索引为 2i + 2
- 如果 2i + 2 > n – 1 ，它无右子节点 堆的接口设计
public interface Heap<E> {
int size();
boolean isEmpty();
void clear();
E get();
void add(E e);
E replace(E e);
E remove();
}堆的数据结构
public class BinaryHeap<E> implements Heap<E> {
private int size;
private E[] elements;
public static final int DEFAULT_CAPACITY = 10;
private Comparator<E> comparator;
public BinaryHeap() {
this(null, null);
}
public BinaryHeap(Comparator<E> comparator) {
this.comparator = comparator;
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}添加元素
将添加的节点加入到数组最后位置，然后循环执行以下操作（图中的80简称为node）
- 如果 node ＞ 父节点，与父节点交换位置
- 如果 node ≤ 父节点，或者 node 没有父节点，退出循环 这个过程，叫做上滤（Sift Up），时间复杂度：O(logn)
代码实现如下：
public void add(E e) {
elementEmptyCheck(e);
elements[size] = e;
siftUp(size);
size++;
}
private void elementEmptyCheck(E e) {
if(null == e) {
throw new IllegalArgumentException("Element must not be null");
}
}
/**
* 从index开始上滤
* @param index
*/
private void siftUp(int index) {
E element = elements[index];
while (index > 0) {
int parentIndex = index >> 1;
E parentElement = elements[parentIndex];
if(compare(element, parentElement) <= 0) {
break;
}
elements[index] = parentElement;
index = parentIndex;
}
elements[index] = element;
}
private int compare(E e1, E e2) {
if(null != comparator) {
return comparator.compare(e1, e2);
}
return ((Comparable) e1).compareTo(e2);
}删除元素
删除的步骤如下
- 用最后一个节点覆盖根节点
- 删除最后一个节点
- 循环执行以下操作（图中的43简称为node）
- 如果 node < 最大的子节点，与最大的子节点交换位置
- 如果 node ≥ 最大的子节点， 或者 node 没有子节点，退出循环
- 这个过程，叫做下滤（Sift Down），时间复杂度：O(logn)
删除操作的代码实现如下：
public E remove() {
int lastIndex = --size;
E element = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return element;
}
/**
* 从index开始下滤
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
while (index < half) { // index必须是非叶子节点
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
if(childIndex + 1 < size) {
if(compare(child, elements[childIndex + 1]) < 0) {
childIndex = childIndex+1;
child = elements[childIndex];
}
}
if(compare(element, child) > 0) {
break;
}
elements[index] = child;
index = childIndex;
}
elements[index] = element;
}替换元素
用新元素替换最大值（第一个元素），操作过程类似删除。
替换操作的代码实现如下：
@Override
public E replace(E e) {
elementEmptyCheck(e);
if(isEmpty()) {
elements[size++] = e;
return null;
}
E oldValue = elements[0];
elements[0] = e;
siftDown(0);
return oldValue;
}构建小顶堆 小顶堆无需新建类，只需要在BinaryHeap的构造方法中，修改一下Comparator的比较策略即可。
可以使用下面的代码构造大顶堆：
BinaryHeap binaryHeap = new BinaryHeap<>((o1, o2) -> o1 - o2); 1 可以使用下面的代码构造小顶堆：
BinaryHeap binaryHeap = new BinaryHeap<>((o1, o2) -> o2 - o1);
举报
腾讯云开发者
