欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Java编程的逻辑】堆与优先级队列&PriorityQueue

程序员文章站 2022-06-05 20:14:46
...

完全二叉树 & 满二叉树 & 堆

基本概念

满二叉树是指除了最后一层外,每个节点都有两个孩子,而最后一层都是叶子节点,都没有孩子。
【Java编程的逻辑】堆与优先级队列&PriorityQueue

满二叉树一定是完全二叉树,但完全二叉树不要求最后一层是满的,但如果不满,则要求所有节点必须集中在最左边,从左到右是连续的,中间不能有空的。

【Java编程的逻辑】堆与优先级队列&PriorityQueue

特点

在完全二叉树中,可以给每个节点一个编号,编号从1开始连续递增,从上到下,从左到右
【Java编程的逻辑】堆与优先级队列&PriorityQueue

完全二叉树有一个重要的特点:给定任意一个节点,可以根据其编号直接快速计算出其父节点和孩子节点。如果编号为i,则父节点编号为i/2,左孩子编号为2*i,右孩子编号为2*i+1
它使得逻辑概念上的二叉树可以方便地存储到数组中,数组中的元素索引就对应节点的编号,树中的父子关系通过其索引关系隐含维持,不需要单独保持。
【Java编程的逻辑】堆与优先级队列&PriorityQueue

这种存储二叉树的方法与之前介绍的TreeMap是不一样的。在TreeMap中,有一个单独的内部类Entry,Entry有三个引用,分别指向父节点、左孩子、右孩子。使用数组存储的优点是节省空间,而且访问效率高。

堆逻辑概念上是一棵完全二叉树,而物理存储上使用数组,还要一定的顺序要求。

TreeMap内部使用的是排序二叉树原理,排序二叉树是完全有序的,每个节点都有确定的前驱和后继,而且不能有重复元素。与排序二叉树不同,在堆中,可以有重复元素,元素间不是完全有序的,但对于父子节点直接,有一定的顺序要求。根据顺序分为两种堆:最大堆、最小堆

最大堆是指每个节点都不大于其父节点。这样,对于每个父节点,一定不小于其所有孩子节点,那么根节点就是所有节点中最大的了。最小堆与最大堆就正好相反,每个节点都不小于其父节点。

【Java编程的逻辑】堆与优先级队列&PriorityQueue

总结来说:堆是完全二叉树,父子节点间有特定顺序,分为最大堆和最小堆,堆使用数组进行物理存储。

堆的操作

添加元素

这里我们以最小堆为例进行讲解

如果堆为空,则直接添加一个根就行了。
如果堆不为空,要在其中添加元素,基本步骤为:
1. 添加元素到最后位置
2. 与父节点比较,如果大于等于父节点,则满足堆的性质,结束。否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点。

该方法称为向上调整
添加一个元素,需要比较和交换的次数最多为树的高度,即log(N)。N为节点数

从头部删除元素

  1. 用最后一个元素替换头部元素,并删掉最后一个元素
  2. 将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束。否则与较小的孩子节点进行交换,交换后,再与较小的孩子节点比较,一直到没有孩子节点或者不大于两个孩子节点。

该方法称为向下调整

从中间删除元素

  1. 与从头部删除一样,先用最后一个元素替换待删元素。
  2. 有两种情况,如果该元素大于某孩子节点,则需要向下调整;如果小于父节点,则需要向上调整。

查找和遍历

在堆中进行查找没有特殊的算法,就是从数组的头找到尾,效率为O(N)

在堆中进行遍历也是类似的。

构建堆

给定一个无序数组,如何使之成为一个最小堆呢?
基本思路是:从最后一个非叶子节点开始,一直往前直到根,对每个节点,执行向下调整。换句话说,自底向上。先使每个最小子树为堆,然后对左右子树和其父节点合并,调整为更大的堆,因为每个子树已经为堆,所以调整就是堆父节点执行向下调整,这样一直合并调整到根。

小结

  1. 在添加和删除元素时,效率为O(logN)
  2. 查找和遍历元素,效率为O(N)
  3. 构建堆的效率是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;
}

小结

  1. 实现了优先级队列,最先出对的总是优先级最高的
  2. 优先级可以有相同的,内部元素不是完全有序的
  3. 查看头部元素效率很高为O(1),入队、出队效率较高为O(logN),构建堆的效率为O(N)
  4. 查找和删除的效率比较低为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;
    }
}