PriorityQueue详解-创新互联

• • 前言
  • PriorityQueue特点
  • API
  • • 构造
    • 操作API
  • 底层显示：数组
  • offer(E e)

PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。

Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

1. PriorityQueue是一个无限制的队列，并且动态增长。默认初始容量’11’可以使用相应构造函数中的initialCapacity参数覆盖。
2. 它不允许NULL对象。
3. 添加到PriorityQueue的对象必须具有可比性。
4. 默认情况下，优先级队列的对象按自然顺序排序。
5. 比较器可用于队列中对象的自定义排序。
6. 优先级队列的头部是基于自然排序或基于比较器的排序的最小元素。当我们轮询队列时，它从队列中返回头对象。
7. 如果存在多个具有相同优先级的对象，则它可以随机轮询其中任何一个。
8. PriorityQueue 不是线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。
9. peek()和element操作是O(1)，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

PriorityQueue（）：使用默认初始容量（11）构造空队列，该容量根据其自然顺序对其元素进行排序。
PriorityQueue（int initialCapacity）：构造具有指定初始容量的空队列，该容量根据其自然顺序对其元素进行排序。
PriorityQueue（int initialCapacity，Comparator comparator）：构造具有指定初始容量的空队列，该容量根据指定的比较器对其元素进行排序。

boolean add（object）：将指定的元素插入此优先级队列。
boolean offer（object）：将指定的元素插入此优先级队列。
boolean remove（object）：从此队列中删除指定元素的单个实例（如果存在）。
Object poll（）：检索并删除此队列的头部，如果此队列为空，则返回null。
Object element（）：检索但不删除此队列的头部，如果此队列为空，则返回null。
Object peek（）：检索但不删除此队列的头部，如果此队列为空，则返回null。
void clear（）：从此优先级队列中删除所有元素。
Comparator comparator（）：返回用于对此队列中的元素进行排序的比较器，如果此队列根据其元素的自然顺序排序，则返回null。
boolean contains（Object o）：如果此队列包含指定的元素，则返回true。
int size（）：返回此队列中的元素数。
Object [] toArray（）：返回包含此队列中所有元素的数组。

上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

public boolean offer(E e) {if (e == null)//不允许放入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);//调用siftUp函数从下往上调整堆
    return true;
}

private void siftUp(int k, E x) {if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {Comparablekey = (Comparable) x;
        while (k >0) {int parent = (k - 1) >>>1;	//拿到父节点
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0) //当前元素>父节点 break
                break;
            queue[k] = e; //当前元素<父节点 父节点元素放置在当前位置，k变成当前父节点，继续下一轮循环，直到当前元素>父节点 break
            k = parent;
        }
        queue[k] = key;//最后把key赋值到正确的位置
    }

当前元素与父节点不断比较如果比父节点小就交换然后继续向上比较，否则停止比较的过程

前言：https://blog.csdn.net/hellokitty136/article/details/105831884/
特点/API：https://twotree.blog.csdn.net/article/details/86503464
源码视频讲解：https://www.bilibili.com/video/BV1tW411j7dL/

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧