# PriorityQueue 源码分析

### PriorityQueue

#### 属性

```    /**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d.  The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access```

```    /**
* 优先级队列元素的个数
*/
private int size = 0;

/**
* 优先级队列结构上被修改的次数。修改操作包括：clear()、offer(E)、poll()、removeAt(int)
*/
transient int modCount = 0; // non-private to simplify nested class access```

#### 方法

• 添加节点
```    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 siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
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;
}```

② 插入“-3”

③ 插入“20”

④ 插入“-25”

• 获取优先级队列头结点
```    public E peek() {
return (size == 0) ? null : (E) queue[0];
}```

• 删除节点
```    public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}```

```    private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}```

```    private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;        // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}```

• 是否包含节点
```    public boolean contains(Object o) {
return indexOf(o) != -1;
}```

```    private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}```
• 移除并获取优先级队列头节点
```    public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}```

• 清除优先级队列中所有节点
```        modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}```

• 迭代器 优先级队列的迭代器并不保证遍历按照指定的顺序获取节点元素。这是因为当在迭代器中执行remove操作时，可能会涉及到一个未访问的元素被移动到了一个已经访问过的节点位置(删除操作时，当队尾节点被放置到待移除节点位置的情况下，需要调用siftUp方法，siftUp(index, object)方法会升高待插入元素在树中的位置index，直到待插入的元素大于或等于它待插入位置的父节点)。在迭代器操作中需要特殊处理。此时这些不幸的元素会在所有节点遍历完后才得以遍历。

### 附

• 证明“在平衡二叉树中，叶子节点的个数总是大于等于前面所有非叶子节点个数之和。” 一个平衡二叉树第N层节点数为：2^N 一个N层的平衡二叉树总节点数为：2^(N+1) -1； Sn = 2^0 + 2^1 + …… + 2^N 2*Sn = 2^1 + 2^2 + …… + 2^N + 2^(N+1) 将二个等式的左边和右边分别进行相减操作得到： (2-1)Sn = 2^(N+1) - 2^0 ==> Sn = 2^(N+1) -1; 所以一个N层的二叉平衡树除了叶子节点外的节点总数最大为：2^N -1； 因而2^N > 2^N -1，所以在满平衡二叉树下，叶子节点大于非叶子节点个数之和，当然在最后一层节点不满的情况下，叶子节点依旧大于等于所有非叶子之和。

0 条评论

• ### Zookeeper

即所谓的配置中心.发布订阅一般有两种设计模式,分别为: Push模式和Pull模式. ZK采用推拉模式相结合的方式: 客户端向服务端注册自己需要监听的节点,一旦...

• ### 图神经网络模型总结

在讨论GNN之前，我们先来了解一下什么是图。在计算机科学中，图是由顶点和边两部分组成的一种数据结构。图G可以通过顶点集合V和它包含的边E来进行描述。

• ### 【二叉树打卡4】二叉树的中序遍历（非递归版）

二叉树的中序遍历顺序是左-根-右。我们可以采用一个栈来辅助，我们把中序遍历的结果放到一个 ArrayList 容器中作为返回值，具体步骤如下：

• ### Selenium系列（十三） - 自动化必备知识之Xpath的详细使用

https://www.cnblogs.com/poloyy/category/1680176.html

• ### 面试官问你B树和B+树，就把这篇文章丢给他

在介绍B+树之前， 先简单的介绍一下B树，这两种数据结构既有相似之处，也有他们的区别，最后，我们也会对比一下这两种数据结构的区别。

• ### 面试官问你 B树 和 B+ 树，就把这篇文章丢给他

在介绍B+树之前， 先简单的介绍一下B树，这两种数据结构既有相似之处，也有他们的区别，最后，我们也会对比一下这两种数据结构的区别。

• ### 十年架构师带你剖析B树和B+树

在介绍B+树之前， 先简单的介绍一下B树，这两种数据结构既有相似之处，也有他们的区别，最后，我们也会对比一下这两种数据结构的区别。