优先队列，堆排序，都用了最小堆
定义
堆是一颗完全二叉树
- 堆中某个结点的值总是不大于或不小于其子结点的值
- 结点小于子结点，最小堆
- 结点大于子结点，最大堆
堆中每个结点的子树都是堆
- 堆不唯一
建堆
使用筛选法建堆。
- 用
siftDown()对当前结点调整，使其作为根结点的子树为为最小堆 - 从最后一个分支结点开始，自下向上执行(1)中的步骤
如下所示为siftDown()方法，从当前结点开始，比较它和它的子结点，如果它大于最小的子结点，就交换它和子结点的值，直至树的最后一层，这样就可以调整为当前结点作为根结点的二叉树为为最小堆。有关父子节点间的索引关系，参见二叉树的性质
void MinHeap::SiftDown(int position) {
int parent = position;
// 左子结点
int child = 2 * parent + 1;
// 当前值暂存
int temp = this->heapArray[parent];
while (child < this->size) {
// 取左右子结点中较小的一个
if (child < this->size - 1 && this->heapArray[child] > this->heapArray[child + 1]) {
child = child + 1;
}
if (temp > this->heapArray[child]) {
// 比暂存值小的结点都向上传播一层
this->heapArray[parent] = this->heapArray[child];
// 向下层继续
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
// 最后再将暂存值放在合适位置
this->heapArray[parent] = temp;
}
建堆时，从最后一个结点开始。最后一个分支结点的下标应为 $\lfloor \frac{n}{2} \rfloor-1$
void MinHeap::buildHeap() {
for (int i = this->size / 2 - 1; i >= 0; i--) {
this->SiftDown(i);
}
}
插入
与 siftDown()类似。siftUp()从当前结点开始，比较它和它的父结点，如果它小于父结点，就交换它和父结点的值，直至第0层
void MinHeap::SiftUp(int position) {
int child = position;
// 父结点
int parent = (child - 1) / 2;
// 当前值暂存
int temp = this->heapArray[child];
while (child > 0) {
if (temp < this->heapArray[parent]) {
// 比暂存值大的结点都向下传播一层
this->heapArray[child] = this->heapArray[parent];
// 向上层继续
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
// 最后再将暂存值放在合适位置
this->heapArray[child] = temp;
}
插入时，将插入的元素放在最后一个叶结点后面，再用 siftUp() 向上传播
bool MinHeap::push(int value) {
if (this->size == this->maxSize) {
return false;
}
this->heapArray[size++] = value;
this->SiftUp(size - 1);
return true;
}
删除
将最后一个叶结点放在根结点位置，并向下传播
bool MinHeap::pop() {
if (size <= 0) {
return false;
}
this->heapArray[0] = this->heapArray[--this->size];
this->siftDown(0);
return true;
}
算法复杂度分析
建堆时间复杂度：$\sum_{i=1}^{log\ n}(i-1)\frac{n}{2^i}=O(n)$
入队：$O(logn)$
删除元素(已知位置)：$O(logn)$
出队: $O(1)$
完整实现
下面使用Java完整实现了一个带泛型并且可以自定义比较器的堆结构
public class Heap<E> {
private final Object[] heap;
private int size = 0;
private final Comparator<? super E> comparator;
public Heap(int size, Comparator<? super E> comparator) {
heap = new Object[size];
this.comparator = comparator;
}
public Heap(Collection<E> data, Comparator<? super E> comparator) {
this.heap = data.toArray(new Object[0]);
this.size = data.size();
this.comparator = comparator;
// 筛选法建堆, 由下往上调用siftDown
// 最后一个分支结点下标为 n/2
for (int i = size / 2 - 1; i >= 0; i--) {
siftDown(i);
}
}
public int size() {
return size;
}
public void add(E val) {
heap[size] = val;
siftUp(size);
size++;
}
public void pop() {
size--;
heap[0] = heap[size];
siftDown(0);
}
public E peek() {
return (E) heap[0];
}
/**
* 从第i个结点向下调整
*/
private void siftDown(int i) {
int parent = i;
// i结点暂存
E record = (E) heap[parent];
// 左子结点
int child = 2 * parent + 1;
while (child < size) {
// 取左右子结点中较小的
if (child + 1 < size && comparator.compare((E) heap[child + 1], (E) heap[child]) < 0) {
child = child + 1;
}
// 当前结点大于子结点则向下传播
if (comparator.compare(record, (E) heap[child]) > 0) {
heap[parent] = heap[child];
} else {
break;
}
// 更新结点索引
parent = child;
child = 2 * parent + 1;
}
heap[parent] = record;
}
/**
* 从第i个结点向上调整
*/
private void siftUp(int i) {
int child = i;
// i结点暂存
E record = (E) heap[child];
// 父结点
int parent = (child - 1) / 2;
// 防止出现child=parent的死循环
while (child > 0) {
// 当前结点小于父结点则将当前结点向上传播
if (comparator.compare(record, (E) heap[parent]) < 0) {
// 给当前结点留出空位
heap[child] = heap[parent];
} else {
break;
}
// 更新结点索引
child = parent;
parent = (child - 1) / 2;
}
heap[child] = record;
}
}
REFERENCE
[1]堆与优先队列 - 北京大学[EB/OL]. Coursera.
文档信息
- 本文作者：wzx
- 本文链接：https://masterwangzx.com/2019/10/25/min-heap/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）