首页 > 极客资料 博客日记
手撸优先队列——二叉堆
2024-10-28 13:00:03极客资料围观12次
在数据结构中,队列可以对应我们生活中的排队现象,像买早点排队,上公共汽车排队等。但是有一些情况,我们要优先某些元素,比如:上公共汽车时,虽然在排队,还是要优先老幼病残孕先上车;当有多个电脑向打印机发送打印请求时,一台电脑要打印100页,而其他电脑都是单页打印,此时更合理的做法时,优先打印单页的请求,最后再打印100页的请求。虽然我们都向往公平,在排队时也讲究先来后到,但是在某些特殊的情况下,还是要允许加塞现象的。这就是今天要给大家讲的——优先队列。
优先队列也是队列,那么最基本的两个操作是必须有的,那就是入队和出队操作。我们能想到的几种简单的实现方法有,比如一个简单的链表,入队时就在链表的最后添加元素,那么出队时就要遍历整个链表,找出最小元素,这显然不是一个好的方案。或者我们直接使用AVL平衡二叉树,最小元素就是最左侧的子节点,很容易找到,但是在入队和出队的过程中,涉及到了节点的增加和删除,那么就要进行树的旋转而维持树的平衡,这额外花费了很多开销。那么有没有相对廉价一点的方案呢?这就是二叉堆的方案。
二叉堆
优先队列的实现使用二叉堆是相当普遍的,二叉堆是一棵二叉树,但是是有要求的二叉树,它是一棵完全二叉树。完全二叉树就是树的节点都是从上到下,从左到右去排列的,而且中间不能隔有空节点。我们看下图中的两个例子:
左图中,J节点并没有按照从左到右依次排列,所以不是完全二叉树,而右图中,满足完全二叉树的特点,是一棵完全二叉树。
二叉堆有连个性质,一个是结构性质,一个是堆序性质。我们先来看结构性质,堆是一棵完全二叉树,是非常有规律的。我们可以直接用数组去表示二叉堆,而不使用链的结构,看下图:
数组中第0个元素我们空着不用,第1个元素是根节点,后面的顺序就是按照完全二叉树的顺序去排。通过观察,我们惊奇的发现了如下的规律,数组中第i个元素的左子节点的位置是2i,右子节点的位置是2i+1,父节点的位置是i/2(根节点除外)。我们可以使用数组的结构表示树,而不是使用链的结构,这使得我们在遍历树的时候操作非常简单。但是数组的结构也有一个问题,那就是数组的长度需要预先估算出来,然后随着数组长度的增加我们还要对其进行扩容操作。这就是二叉堆的结构性质,我们可以使用数组去表示。
接下来我们再看看堆序性质,由于我们快速的找到最小元素,那么最小元素我们要放到根节点上。同理,我们考虑到任意子树也是一个二叉堆,那么子树中的最小元素应当在子树的根节点。那么也就是任意节点都应该小于它的后代节点。所以二叉堆的堆序性质就是,对于二叉堆中的任意节点,它的父节点要小于或等于该节点。我们再看下面两个例子:
左图中节点6的父节点是21,小于6,不满足堆序性质,所以左图不是二叉堆。右图满足堆序性质,是二叉堆。
插入
当我们向二叉堆中插入一个新的元素时,为了满足二叉堆从上到下,从左到右的性质,我们先确定插入元素的位置,然后再和该位置的父节点作比较,如果大于父节点,那么是满足二叉堆性质的,直接插入就好了;如果不满足,则需要交换两个元素的位置,交换后再去和父节点作比较,就这样一直递归下去,直到满足二叉堆性质为止,或者交换到了根节点,是二叉堆中的最小元素。还使用上面的例子,比如我们要插入新的元素14,
由于14小于21,需要继续向上调整,
调整到这个位置时,满足了二叉堆的性质,我们把14插入。这样的一个整个过程就做上滤。下面我们编写程序实现这一过程。
/**
* 二叉堆
* @param <T>
*/
public class BinaryHeap<T extends Comparable<T>> {
private static final int DEFAULT_CAPACITY = 10;
private int currentSize;
private T[] array;
public BinaryHeap() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public BinaryHeap(int defaultCapacity) {
this.currentSize = 0;
this.array = (T[])new Comparable[defaultCapacity];
}
/**
* 二叉堆是否为空
* @return
*/
public boolean isEmpty() {
return this.currentSize == 0;
}
/**
* 使二叉堆为空
*/
@SuppressWarnings("unchecked")
public void makeEmpty() {
this.currentSize = 0;
this.array = (T[])new Comparable[DEFAULT_CAPACITY];
}
/**
* 扩展数组
* @param newSize 扩展数组大小
*/
@SuppressWarnings("unchecked")
private void enlargeArray(int newSize) {
if (newSize < this.array.length) {
throw new RuntimeException("扩展数组小于原始数组");
}
T[] tmpArray = (T[])new Comparable[newSize];
System.arraycopy(this.array,0,tmpArray,0,this.array.length);
this.array = tmpArray;
}
/**
* 二叉堆插入元素
* @param element 插入元素
*/
public void insert(T element) {
if (currentSize == this.array.length-1) {
enlargeArray(this.array.length * 2 - 1);
}
int hole = ++currentSize;
for (this.array[0] = element;element.compareTo(this.array[hole/2]) < 0;hole /= 2) {
this.array[hole] = this.array[hole/2];
}
this.array[hole] = element;
}
}
由于二叉堆中的元素是可比较的,所以我们定义了泛型,必须实现了Comparable
接口。然后我们定义数组array
,和数组的初始长度DEFAULT_CAPACITY
。最后再定义二叉堆当前的节点数currentSize
。两个构造函数和isEmpty
、makeEmpty
方法比较简单,这里不做过多介绍了。接下来我们看一下数据扩容的方法enlargeArray
,先比较一下新的长度和数组当前长度,如果小于,则抛出异常。然后就是创建新数据,数据复制,替换老数据。
接下来我们重点看一下insert
方法,先判断currentSize
和数组长度-1,这里为什么要减1呢?因为数据的第0个元素是不用的,二叉堆的根节点在第1个元素。如果相等,说明数组已经用尽,需要扩容,扩容的时候也是采用2倍扩容,这里减1还是因为不用根节点。然后先确定空穴的位置,hole=++currentSize
,下面的for循环,就是上滤的过程,也是这一段的精华。大家在实现的时候,可能都会和父元素作比较,然后进行交换,这种方法没有问题,但是交换两个元素要用3行代码来完成,先把第一个变量赋值给临时变量,再把第二个变量赋值给第一个变量,最后把临时变量赋值给第二个变量。而这里只使用了1行代码,这就是使用空穴位置的好处。在for循环中,将新元素赋值给第0个元素,这里使用第0个元素是有用处的,我们接着看,然后新元素和父节点作比较,父节点的下标是hole/2,这个在前面介绍过,如果小于,当前空穴位置的值就是父节点的值,然后处理空穴的位置,就是父节点的位置,hole /=2。如果这样一直到了根节点,也就是hole=1的时候,父节点是不存在的,但是程序中写的是hole/2,那么就是第0个元素,第0个元素就是新插入的元素,等于是自己和自己比较,是相等的,所以就跳出了循环。最后把空元素的值赋给空穴位置。这里我们巧妙的使用第0个元素,实现了根节点的比较,使得跳出循环。
删除最小值
删除最小值,就是我们的出队操作,由于我们使用二叉堆,所以最小值就在根节点,删除之后,在根节点产生了一个空穴,我们把二叉堆的最后一个元素,也就是currentSize的元素放到空穴位置,再和两个子节点的最小元素作比较,如果大于,则交换两个元素,空穴位置下移,直到满足二叉堆的性质为止。这个过程叫下滤。
删除根节点13后,产生一个空穴,同时,整个数组长度减1,我们用最后一个元素31,和空穴的最小子节点14作比较,31大于14,所以交换位置,如下:
继续比较,31大于最小子节点21,空穴位置下移,
最后,31小于子节点32,那么31就放在空穴位置,满足了二叉堆的性质,整个下滤过程结束。我们用代码实现一下,
/**
* 取出最小值
* @return 根元素
*/
public T deleteMin() {
if (isEmpty()) {
throw new RuntimeException("二叉堆为空");
}
T minItem = this.array[1];
this.array[1] = this.array[currentSize--];
perlocateDown(1);
return minItem;
}
/**
* 下滤过程
* @param hole
*/
private void perlocateDown(int hole) {
int child;
T tmp = this.array[hole];
for (;hole * 2 <= currentSize;hole=child) {
child = hole * 2;
if (child != currentSize && this.array[child].compareTo(this.array[child+1]) > 0) {
child += 1;
}
if (this.array[child].compareTo(tmp) < 0) {
this.array[hole] = this.array[child];
} else {
break;
}
}
this.array[hole] = tmp;
}
deleteMin
方法很简单,就是取根节点元素,将最后一个元素赋值给根节点,节点个数减1,然后调用下滤方法。我们重点要看的就是下滤方法,入参是空穴的位置,传入的是1,也就是根节点的位置,我们将值赋给临时变量,这里根节点的值是二叉堆的最后一个元素。接下来我们进入循环,循环成立的条件是空穴位置有子节点,hole*2 <= currentSize
。那么左子节点的位置是hole*2,右子节点是hole*2+1。这里我们特殊处理的是空穴是不是只有一个子节点,只有一个子节点的情况只会发生在二叉堆的最后的位置,如果hole*2 == currentSize
,说明后只有一个子节点,而且只能是左子节点,这样,我们就能够找出hole的最小子节点了,判断的逻辑是:如果hole*2 == currentSize
,那么hole只有一个左子节点,最小子节点就是hole*2;其他情况就需要比较左右子节点,谁小就用谁。这就是我们for循环中第一个if处的逻辑。后面的逻辑就比较简单了,如果hole的值大于最小子节点,就进行交换,hole下移,等于最小子节点的位置,直到跳出循环。最后将临时值赋给空穴位置。这就是整个的删除和下滤的过程。
构建二叉堆
最重点的插入和删除方法我们已经讲完了,那么如果给我们一个数组,我们怎么去构建一个二叉堆呢?我们还是要从二叉堆的性质入手,也就是结构性质和堆序性质。结构性质比较容易我们将第0个元素空着就可以了,那么堆序性质怎么解决呢?由于上面我们已经将下滤过程抽象成了一个方法,这也就不难实现了。我们先将最小的子树,通过下滤方法变成二叉堆,最小的子树的节点就是树中倒数第二层的节点,倒数第二层的节点中,有的节点有子节点,有的节点没有子节点,没有子节点的不用下滤,那么怎么找到有子节点的节点呢?我们之前有个变量currentSize,这是最后一个节点的位置,它的父节点是currentSize/2,也是最后一个有子节点的节点,然后我们向前循环,每个节点执行一遍下滤方法,直到根节点下滤完,那么整棵树就是一个二叉堆了。我们实现一下,
/**
* 构建二叉堆
* @param items
*/
@SuppressWarnings("unchecked")
public BinaryHeap(T[] items) {
this.currentSize = items.length;
this.array = (T[])new Comparable[this.currentSize * 2 +1];
int i = 1;
for (T item: items) {
this.array[i++] = item;
}
buildHeap();
}
/**
* 构建二叉堆
*/
private void buildHeap() {
for (int i = this.currentSize / 2;i>0;i--) {
perlocateDown(i);
}
}
实现起来很简单,这里注意一下循环的时候,条件是i>0
,不是大于等于,因为第0个元素是不用的。
总结
好了,到这里二叉堆就介绍完了,它是实现优先队列最基本的方法,有问题的小伙伴欢迎评论区留言~~
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”