【Java编程的逻辑】堆与优先级队列&PriorityQueue
完全二叉树 & 满二叉树 & 堆
基本概念
满二叉树是指除了最后一层外,每个节点都有两个孩子,而最后一层都是叶子节点,都没有孩子。
满二叉树一定是完全二叉树,但完全二叉树不要求最后一层是满的,但如果不满,则要求所有节点必须集中在最左边,从左到右是连续的,中间不能有空的。
特点
在完全二叉树中,可以给每个节点一个编号,编号从1开始连续递增,从上到下,从左到右
完全二叉树有一个重要的特点:给定任意一个节点,可以根据其编号直接快速计算出其父节点和孩子节点。如果编号为i,则父节点编号为i/2,左孩子编号为2*i,右孩子编号为2*i+1
它使得逻辑概念上的二叉树可以方便地存储到数组中,数组中的元素索引就对应节点的编号,树中的父子关系通过其索引关系隐含维持,不需要单独保持。
这种存储二叉树的方法与之前介绍的TreeMap是不一样的。在TreeMap中,有一个单独的内部类Entry,Entry有三个引用,分别指向父节点、左孩子、右孩子。使用数组存储的优点是节省空间,而且访问效率高。
堆
堆逻辑概念上是一棵完全二叉树,而物理存储上使用数组,还要一定的顺序要求。
TreeMap内部使用的是排序二叉树原理,排序二叉树是完全有序的,每个节点都有确定的前驱和后继,而且不能有重复元素。与排序二叉树不同,在堆中,可以有重复元素,元素间不是完全有序的,但对于父子节点直接,有一定的顺序要求。根据顺序分为两种堆:最大堆、最小堆
最大堆是指每个节点都不大于其父节点。这样,对于每个父节点,一定不小于其所有孩子节点,那么根节点就是所有节点中最大的了。最小堆与最大堆就正好相反,每个节点都不小于其父节点。
总结来说:堆是完全二叉树,父子节点间有特定顺序,分为最大堆和最小堆,堆使用数组进行物理存储。
堆的操作
添加元素
这里我们以最小堆为例进行讲解
如果堆为空,则直接添加一个根就行了。
如果堆不为空,要在其中添加元素,基本步骤为:
1. 添加元素到最后位置
2. 与父节点比较,如果大于等于父节点,则满足堆的性质,结束。否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点。
该方法称为向上调整
添加一个元素,需要比较和交换的次数最多为树的高度,即log(N)。N为节点数
从头部删除元素
- 用最后一个元素替换头部元素,并删掉最后一个元素
- 将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束。否则与较小的孩子节点进行交换,交换后,再与较小的孩子节点比较,一直到没有孩子节点或者不大于两个孩子节点。
该方法称为向下调整
从中间删除元素
- 与从头部删除一样,先用最后一个元素替换待删元素。
- 有两种情况,如果该元素大于某孩子节点,则需要向下调整;如果小于父节点,则需要向上调整。
查找和遍历
在堆中进行查找没有特殊的算法,就是从数组的头找到尾,效率为O(N)
在堆中进行遍历也是类似的。
构建堆
给定一个无序数组,如何使之成为一个最小堆呢?
基本思路是:从最后一个非叶子节点开始,一直往前直到根,对每个节点,执行向下调整。换句话说,自底向上。先使每个最小子树为堆,然后对左右子树和其父节点合并,调整为更大的堆,因为每个子树已经为堆,所以调整就是堆父节点执行向下调整,这样一直合并调整到根。
小结
- 在添加和删除元素时,效率为O(logN)
- 查找和遍历元素,效率为O(N)
- 构建堆的效率是O(N)
PriorityQueue
PriorityQueue是优先级队列,实现了队列接口(Queue),内部是用堆实现的,内部元素不是完全有序的,不过,逐个出对会得到有序的输出。
基本用法
PriorityQueue有多个构造方法:
public PriorityQueue();
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
public PriorityQueue(Collection<? extends E> c);
PriorityQueue是用堆实现的,堆物理上就是数组,与ArrayList类似,都是使用动态数据,根据元素的个数进行动态扩展,initialCapacity表示初始化的数组大小,默认为11。与TreeMap/TreeSet类似,为了保持一定顺序,PriorityQueue要求要么元素实现Comparable接口,要么传递一个比较器Comparator。
实现原理
先看看内部组成成员:
// 实际存储元素的数组
private transient Object[] queue;
// 当前元素个数
private int size = 0;
// 比较器,可以为null
private final Comparator<? super E> comparator;
// 修改次数
private transient int modCount = 0;
构造方法上面已经提到过了,主要是初始化queue和comparator 。 操作相关的代码和上面的堆的操作差不多的,这里我们以入队为例,做一个简单的讲解
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 确保数组长度是够的
if (i >= queue.length)
grow(i + 1);
// 元素长度增加
size = i + 1;
// 如果第一次添加,直接放在第一个位置
if (i == 0)
queue[0] = e;
// 否则将其放入最后一个位置,并向上调整
else
siftUp(i, e);
return true;
}
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
// 如果原来长度比较小,扩展为两倍,否则就增加50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
/**
* 向上调整
*/
private void siftUp(int k, E x) {
// 如果有比较器就用比较器
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
/**
* 向上寻找x真正应该插入的位置
* @param k 表示插入的位置
* @param x 表示新元素
*/
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
// 父节点位置,当前节点位置/2
int parent = (k - 1) >>> 1;
// 父节点
Object e = queue[parent];
// 如果新元素大于等于父节点,则满足堆的性质,退出
if (comparator.compare(x, (E) e) >= 0)
break;
// 否则父元素下移,继续向上寻找
queue[k] = e;
k = parent;
}
queue[k] = x;
}
小结
- 实现了优先级队列,最先出对的总是优先级最高的
- 优先级可以有相同的,内部元素不是完全有序的
- 查看头部元素效率很高为O(1),入队、出队效率较高为O(logN),构建堆的效率为O(N)
- 查找和删除的效率比较低为O(N)
堆和PriorityQueue的应用
问题
这里先抛出两个比较常见的问题,然后再用堆的思想来进行解决
1. 求前K个最大的元素,元素个数不确定,数据量可能很大,甚至源源不断到来,但需要知道目前为止最大的前K个元素
2. 求中值元素,中值不是平均值,而是排序后中间那个元素的值,同样数据量可能很大,甚至源源不断到来
求前K个最大的元素
一个简单的思路是排序,排序后取最大的K个就可以了,排序可以使用Arrays.sort()方法,效率为O(N*log(N))。Arrays.sort()使用的是经过调优的快速排序法 。
另一种思路是选择,循环选择K次,每次从剩下的元素中选择最大值,效率为O(N*K),如果K值大于log(N),就不如排序了。
不过这两个思路都是假定所有元素都是已知的,而不是动态的。如果元素个数不确定,且源源不断到来呢?
一个基本的思路是维护一个长度为K的数组,最前面的K个元素就是目前最大的K个元素,以后每来一个新元素的时候,都先找到数组中最小值,将新元素与最小值相比,如果小于最小值,什么都不用做;如果大于最小值,则将最小值替换为新元素。
这类似于生活中常见的末尾淘汰。
这样,数组中维护的永远都是最大的K个元素,不管数据源有多少,需要的内存开销是固定的,就是长度为K的数组。不过,每来一个元素,都需要找最小值,都需要进行K次比较,能不能减少比较次数呢?
解决方法是使用最小堆维护这个K个元素,最小堆中,根即第一个元素永远都是最小的,新来的元素与根比较就可以了,如果小于根,则堆不需要变化,否则用新元素替换根,然后向下调整堆即可,调整的效率为O(logK),总体效率就是O(N*logK)。而且使用了最小堆后,第K个最大的元素也很容易获取,它就是堆的根
public class TopK<E> {
private PriorityQueue<E> p;
private int k;
public TopK(int k) {
this.k = k;
this.p = new PriorityQueue<>(k);
}
public void addAll(Collection<? extends E> c) {
for(E e: c) {
add(e);
}
}
public void add(E e) {
if(p.size() < k) {
p.add(e);
return ;
}
Comparable<? super E> head = (Comparable<? super E>)p.peek();
if(head.compareTo(e)>0) {
// 小于TopK中的最小值,不用变
return ;
}
// 新元素替换掉原来最小值成为TopK之一
p.poll();
p.add(e);
}
public <T> T[] toArray(T[] a) {
return p.toArray(a);
}
public E getKth() {
return p.peek();
}
}
求中值
中值就是排序后中间那个元素的值,如果元素个数为奇数,中值是没有歧义的,如果是偶数,可以为偏小的,也可以为偏大的。
一个简单的思路就是排序,排序后取中间的那个值就可以了。排序可以使用Arrays.sort()方法,效率为O(N*log(N))。
当然,这是要在数据源已知的情况下才能做到的。如果数据源源不断到来呢?
可以使用两个堆,一个最大堆,一个最小堆
1. 假设当前的中位数为m,最大堆维护的是<=m的元素,最小堆维护的是>=m的元素,但两个堆都不包含m。
2. 当新的元素到达时,比如为e,将e与m进行比较,若e<=m,则将其加入最大堆中,否则加入最小堆中
3. 如果此时最小堆和最大堆的元素个数相差>=2,则将m加入元素个数少的堆中,然后从元素个数多的堆将根节点移除并赋值给m。
给个示例解释一下,输入的元素依次是:34,90,67,45,1
1. 输入第一个元素时,m赋值为34
2. 输入第二个元素时,90>34,把90加入最小堆,m不变
3. 输入第三个元素时,67>34,把67加入最小堆,此时最小堆根节点为67。但是现在最小堆中元素个数为2,最大堆中元素个数为0,所以需要做调整,把m(34)加入个数少的堆中(最大堆),然后从元素个数多的堆(最小堆)将根节点移除并赋值给m,所以现在m为67,最大堆中有34,最小堆中有90
4. 输入第四个元素时,45<67,把45加入最大堆,m不变
5. 输入第五个元素时,1<67,把1加入最大堆中,此时m为67,最大堆中有1,34,45,最小堆中有90,所以需要调整。调整后,m为45,最大堆为1,34,最小堆为67,90。
public class Median<E> {
// 最小堆
private PriorityQueue<E> minP;
// 最大堆
private PriorityQueue<E> maxP;
// 中值
private E m;
public Median() {
this.minP = new PriorityQueue<>();
this.maxP = new PriorityQueue<>(11, Collections.reverseOrder());
}
// 比较
private int compare(E e, E m) {
Comparable<? super E> cmpr = (Comparable<? super E>)e;
return cmpr.compareTo(e);
}
public void add(E e) {
if(m == null) {
// 第一个元素
m = e;
return ;
}
if(compare(e, m) < 0) {
// 如果e小于m,则加入最大堆
maxP.add(e);
} else {
// 如果e大于m,则加入最小堆
minP.add(e);
}
if(minP.size() - maxP.size() >= 2) {
// 最小堆中元素比最大堆中元素多2个
// 将m加入最大堆中,然后将最小堆中的根移除赋值给m
maxP.add(this.m);
this.m = minP.poll();
} else if(maxP.size() - minP.size() >= 2) {
minP.add(this.m);
this.m = maxP.poll();
}
}
public void addAll(Collection<? extends E> c) {
for(E e : c) {
add(e);
}
}
public E getM() {
return m;
}
}
下一篇: 数据结构与算法(十四)