一、二叉堆（Heap）
1、思考
- 设计一种数据结构，用来存放整数，要求提
3个接口。- 添加元素
- 获取最大值
- 删除最大值
image
- 更优秀的数据结构：
堆，获取最大值复杂度O(1)，删除最大值O(logn)，添加元素O(logn)
2、概念
- 堆（Heap）也是一种树状的数据结构
- 堆的一个重要性质：任意节点的值总是
大于等于或小于等于子节点的值。-
如果任意节点的值总是大于等于子节点的值，称为
最大堆，大根堆，大顶堆。image 反之称为
最小堆，小根堆，小顶堆。
-
image
- 最大堆和最小堆的最大值/最小值都在顶部。且堆中的元素必须具备可比较性。
3、堆的接口设计
public interface Heap<E> {
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void add(E element); // 添加元素
E get(); // 获得堆顶元素
E remove(); // 删除堆顶元素
E replace(E element); // 删除堆顶元素的同时插入一个新元素
}
复制代码
二、二叉堆（Binary Heap）
-
二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆。
image
- 鉴于完全二叉树的一些性质，二叉堆的底层（物理结构）一般用数组实现即可。
- 索引i的规律（n是元素数量）
- 如果
i = 0，它是根节点。 - 如果
i > 0，它的父节点的索引为floor((i-1) / 2)。 - 如果
2i + 1 <= n - 1，它的左子节点的索引为2i + 1。 - 如果
2i + 1 > n - 1，它无左子节点。 - 如果
2i + 1 <= n - 1，它的右子节点的索引为2i + 2`。 - 如果
2i + 1 > n - 1，它无右子节点。
- 如果
三、二叉堆（Binary Heap）接口实现
1、构造函数
public BinaryHeap(E[] elements, Comparator<E> comparator) {
super(comparator);
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[I];
}
heapify();
}
}
复制代码
2、添加
image
- 添加操作需要循环执行以下步骤：
- 如果
node > 父节点，则与父节点交换位置。 - 如果
node <= 父节点，或者node没有父节点，则退出循环。
- 如果
- 这个过程叫做
上滤（Sift Up），时间复杂度为O(logn)。
image
@Override
public void add(E element) {
elementNotNullCheck(element); //非空判断
ensureCapacity(size + 1); //扩容代码
elements[size++] = element;
siftUp(size - 1);
}
//非空判断
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
// 扩容
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[I];
}
elements = newElements;
}
//上滤
/**
* 让index位置的元素上滤
* @param index
*/
private void siftUp(int index) {
E element = elements[index]; //先备份一份节点的值
while (index > 0) {
int parentIndex = (index - 1) >> 1; //获取父节点索引
E parent = elements[parentIndex]; //获取父节点的内容
if (compare(element, parent) <= 0) break;
// 将父元素存储在index位置
elements[index] = parent;
// 重新赋值index
index = parentIndex;
}
elements[index] = element; //当最终确认交换位置后，再将备份的值赋给新的位置。
}
复制代码
3、删除
- 用最后一个节点覆盖根节点
- 删除最后一个节点
- 循环执行以下步骤（
43简称为node）- 如果
node < 最大的子节点，与最大的子节点交换位置。 - 如果
node >= 最大的子节点，或者node没有子节点，则退出循环。
- 如果
- 这个过程叫做
下滤（Sift Down），时间复杂度：O(logn)。
image
- 同样的，交换位置的操作可以像添加那样进行优化。
@Override
public E remove() {
emptyCheck();
int lastIndex = --size; //最后一个元素的索引
E root = elements[0]; //拿出0位置的元素
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0); //下滤
return root;
}
/**
* 让index位置的元素下滤
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一个叶子节点的索引 == 非叶子节点的数量
// index < 第一个叶子节点的索引
// 必须保证index位置是非叶子节点
while (index < half) {
// index的节点有2种情况
// 1.只有左子节点
// 2.同时有左右子节点
// 默认为左子节点跟它进行比较
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
// 选出左右子节点最大的那个
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) >= 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置index
index = childIndex;
}
elements[index] = element;
}
复制代码
4、replace操作
- 删除堆顶元素，并用新值替换。
- 用新值替换堆顶，然后做
下滤操作即可。
@Override
public E replace(E element) {
elementNotNullCheck(element);
E root = null;
if (size == 0) {
elements[0] = element;
size++;
} else {
root = elements[0]; //保存要删除的元素
elements[0] = element; //替换堆顶元素
siftDown(0); // 下滤
}
return root;
}
复制代码
5、批量建堆
- 批量建堆有两种做法
- 自上而下的上滤
- 自下而上的下滤
- 自上而下的上滤：从上而下拿到每个元素，然后上滤。
image
- 自下而上的下滤：从下而上拿到每个元素，然后下滤。
- 叶子节点无须下滤，所以从第一个非叶子节点开始操作。
image
- 效率比较：
image
- 下滤执行最长操作的元素最少，而上滤需要执行最长操作的元素非常多。所以下滤效率更高。
