思考 假如需要设计一种数据结构,用来存放整数,要求提供3个接口:
有没有更优的数据结构?使用堆,可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。
堆的介绍 堆(Heap)也是一种树状的数据结构(不要跟java内存模型中的“堆空间”混淆),常见的堆实现有:
堆的性质:任意节点的值总是 ≥( ≤ )子节点的值
二叉堆(Binary Heap) 二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆。
鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可。
数组中索引i的规律(n是元素数量):
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)
代码实现如下:
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);
}
删除的步骤如下
删除操作的代码实现如下:
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);