手撸一个优先队列

前言

我们在日常开发中时常使用到优先队列这个结构,它可以帮助我们将添加到集合中的元素按指定的优先级排序,真是十分好用的一个结构。虽然对它底层的实现原理有些了解,但是我还是忍不住想自己动手实现一个优先队列。

实现功能

JDK中的PriorityQueue的功能比较多,但我们的优先队列只实现一些核心的功能:

  1. 泛型,支持任意元素
  2. 可自定义比较器,支持自定义元素的优先顺序
  3. 对象数组存储元素,需实现扩容方式
  4. 通过堆维护元素顺序
  5. 先进先出,非双端队列
  6. 迭代器访问,和支持 foreach 遍历
  7. fast-fail 机制

优先级原理

优先队列底层是通过一个对象数组来存储数据,但是逻辑上却是通过堆结构来组织数据。通过维护一个小顶堆,从而实现了每次取元素都是优先级最高的。

为了维护小顶堆,向队列写入元素时,需要向上调整;从队列中弹出元素时,需要向下调整。细节请看下面源码:

注意:堆顶在数组头方向,不能选择放在队尾,因为那样的话,弹出堆顶然后向下调整时,数组头部会空出位置。

/**
 * 向上调整
 *
 * @param i 调整的元素下标
 * @param e 调整的
 元素值
 */
private void siftUp(int i, E e) {
    while (i > 0) {
        int parent = (i - 1) >> 1;
        Object p = queue[parent];
        if (comparator.compare(e, (E) p) > 0)
            break;
        queue[i] = p;
        i = parent;
    }
    queue[i] = e;
}

/**
 * 向下调整
 *
 * @param i 调整的元素下标
 * @param e 调整的元素值
 */
private void siftDown(int i, E e) {
    int half = size >> 1; // only need to traverse non-leaf node
    while (i < half) {
        queue[i] = e;
        int l = (i << 1) + 1, r = l + 1, g = i;
        if (l < size && comparator.compare((E) queue[l], (E) queue[g]) < 0)
            g = l;
        if (r < size && comparator.compare((E) queue[r], (E) queue[g]) < 0)
            g = r;
        if (g == i)
            break;
        queue[i] = queue[g];
        i = g;
    }
    queue[i] = e;
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i == cap)
        grow();
    siftUp(i, e);
    size++;
    return true;
}

public E poll() {
    final Object result;
    if ((result = queue[0]) != null) {
        modCount++;
        Object e = queue[--size];
        queue[size] = null;
        siftDown(0, (E) e);
    }
    return (E) result;
}

迭代器访问

通过创建实现Iterator接口的内部类可实现迭代器访问。如果要支持 foreach 遍历方式,需要让优先队列实现Iterable类,即实现一个返回iterator对象的方法。

实现源码

源码请看GitHub仓库:
github - MyPriorityQueue

如果访问速度太慢,可访问Gitee
gitee - MyPriorityQueue

手撸一个优先队列

上一篇:阿里云服务器选择及使用体验!


下一篇:ceph报错"mon.node3 low disk space"