持有对象--PriorityQueue

Leefs 2019-12-10 AM 1998℃ 0条

# 持有对象--PriorityQueue

### 前言

本篇将讲述《Java编程思想》第11.11.1小节，PriorityQueue

### PriorityQueue简介

1. 1.Queue（队列）和PriorityQueue(优先级队列)比较：

> Queue:先进先出（FIFO）
>
> PriorityQueue(优先级队列)：通过比较器控制元素的输出顺序（优先级）

PriorityQueue是Queue的子类。

2. 2.PriorityQueue是如何进行排序的？

> 1. 放入队列的元素实现了Comparable接口，按照其自然顺序排序，从小到大
> 2. 初始化队列时指明Comparator外部比较器

```
PriorityQueue<String> queue1 = new PriorityQueue<>();
PriorityQueue<String> queue2 = new PriorityQueue<>(10);
PriorityQueue<String> queue3 = new PriorityQueue<>((a,b)->a.compareTo(b));
```

3. 3.PriorityQueue内部结构？

PriorityQueue内部使用数组存放元素

```java
transient Object[] queue;
```

数组默认容量11 （初始化时可以指定）

**动态扩容机制**

容量<64 扩容为2*n+2,否则跟ArrayList一样扩大为1.5n

```java
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 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);
}
```

**小根堆实现**

小根堆：是一种完全二叉树，且满足父节点不大于任意一个左右子节点。（注意左右节点是没有顺序的）

所以小根堆的顶点必然是最小的 （如何要实现从大到小排序，指定的Comparator中取相反顺序即可）

而完全二叉树(所有节点满足从左到右排列 不会垮节点)是可以用数组表示的。

PriorityQueue就是使用数组来实现的小根堆： 满足每次取的数据都是最小的，**但不满足整体都是有序的**。

![PriorityQueueDemo01.png][1]

任意一个节点(数组中索引为n） 都可以知道其左右子节点和父节点在数组中的索引值：

> 父节点 : (n-1)/2
>
> 左子节点: 2n+1
>
> 右子节点:2n+2

**节点的增删**

> 增：在完全二叉树中依次创建一个新节点，再把新节点跟父节点依次比较，使其满足最小堆要求
>
> 删：删除的节点，用二叉树的最后一个节点先填充，再进行调整。

4. 4.PriorityQueue的构造方法摘要

| 方法                                                         | 说明                                                         |
   | ------------------------------------------------------------ | ------------------------------------------------------------ |
   | PriorityQueue()                                              | 使用默认的初始容量（11）创建一个 `PriorityQueue`，并根据其自然顺序对元素进行排序。 |
   | PriorityQueue(Collection<? extends E> c)                     | 创建包含指定 collection 中元素的 `PriorityQueue`。           |
   | PriorityQueue(int initialCapacity)                           | 使用指定的初始容量创建一个 `PriorityQueue`，并根据其自然顺序对元素进行排序。 |
   | PriorityQueue(int initialCapacity, Comparator<? super E> comparator) | 使用指定的初始容量创建一个 `PriorityQueue`，并根据指定的比较器对元素进行排序。 |
   | PriorityQueue(PriorityQueue<? extends E> c)                  | 创建包含指定优先级队列元素的 `PriorityQueue`。               |
   | PriorityQueue(SortedSet<? extends E> c)                      | 创建包含指定有序 set 元素的 `PriorityQueue`。                |

5. 5.常用方法

| 方法                      | 方法说明                                         |
   | ------------------------- | ------------------------------------------------ |
   | public boolean add（E e） | 将指定的元素插入此优先级队列。不能添加null元素。 |
   | public boolean offer(E e) | 将指定的元素插入此优先级队列。不能添加null元素。 |

#### add与offer图解

![PriorityQueueDemo02.png][2]

| 方法        | 方法说明                                             |
| ----------- | ---------------------------------------------------- |
| peek()      | 获取队列顶部元素——仅仅获取，没有删除                 |
| element（） | 获取堆顶元素——队列为空抛异常NoSuchElementException() |

#### peek与element图解

**element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null**

![PriorityQueueDemo03.png][3]

| 方法       | 方法说明                                                     |
| ---------- | ------------------------------------------------------------ |
| remove（） | 删除堆顶元素——队列为空的时候抛出异常NoSuchElementException() |
| poll（）   | 删除元素：删除堆顶元素——队列为空的时候返回null               |

#### remove()与poll()图解

**remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。**

![PriorityQueueDemo04.png][4]

![staticdemo07.png][5]

### 代码示例

```java
public class PriorityQueueDemo {
    public static void main(String[] args) {
        //创建一个PriorityQueue对象
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
        Random rand = new Random(47);
        for(int i =0; i< 10 ;i++){
            priorityQueue.offer(rand.nextInt(i+10));
        }
        QueueDemo.printQ(priorityQueue);
        List<Integer> ints = Arrays.asList(25,22,20,18,14,9,3,1,1,2,3,9,14,18,21,23,25);
        priorityQueue = new PriorityQueue<Integer>(ints);
        QueueDemo.printQ(priorityQueue);
        priorityQueue = new PriorityQueue<Integer>(ints.size(), Collections.reverseOrder());
        priorityQueue.addAll(ints);
        QueueDemo.printQ(priorityQueue);

String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
        List<String> strings = Arrays.asList(fact.split(" "));
        PriorityQueue<String> stringsPQ = new PriorityQueue<String>(strings);
        QueueDemo.printQ(stringsPQ);
        stringsPQ = new PriorityQueue<String>(strings.size(),Collections.reverseOrder());
        stringsPQ.addAll(strings);
        QueueDemo.printQ(stringsPQ);

Set<Character> charSet = new HashSet<Character>();
        for(char c:fact.toCharArray()){
            charSet.add(c);
        }
        PriorityQueue<Character> characterPQ = new PriorityQueue<Character>(charSet);
        QueueDemo.printQ(characterPQ);
    }
}
```

> 运行结果

```java
0   1   1   1   1   1   3   5   8   14   
1   1   2   3   3   9   9   14   14   18   18   20   21   22   23   25   25   
25   25   23   22   21   20   18   18   14   14   9   9   3   3   2   1   1   
EDUCATION   ESCHEW   OBFUSCATION   SHOULD   
SHOULD   OBFUSCATION   ESCHEW   EDUCATION   
    A   B   C   D   E   F   H   I   L   N   O   S   T   U   W   
```

从上方代码你可以看到，重复是充许的，最小的值拥有最高的优先级（如果是String，空格也可以算作值 ，并且比字母的优先级高）。

*附：[参考文章链接1](https://www.cnblogs.com/yangfei629/p/11567941.html)*、[参考文章链接2](https://blog.csdn.net/qq_43776742/article/details/92831821)

[1]: https://lilinchao.com/usr/uploads/2019/12/2874468497.png
  [2]: https://lilinchao.com/usr/uploads/2019/12/776478523.png
  [3]: https://lilinchao.com/usr/uploads/2019/12/2279102075.png
  [4]: https://lilinchao.com/usr/uploads/2019/12/2613585622.png
  [5]: https://lilinchao.com/usr/uploads/2019/12/1907277367.png

标签: Java, Java编程思想, JavaSE, 持有对象

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/274.html

上一篇持有对象--Queue

下一篇持有对象--Collection和Iterator

持有对象--PriorityQueue

评论已关闭

栏目分类

标签云

友情链接申请

持有对象--PriorityQueue

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请