PriorityQueue作用

PriorityQueue（优先队列）是Java中的一种数据结构，它是一种特殊的队列，其中的元素按照一定的优先级进行排列。与普通队列不同，优先队列中的元素不是按照它们被添加到队列的顺序出队，而是按照它们的优先级出队。优先队列通常使用堆（heap）数据结构来实现，以保证高效地插入和删除操作。

优先队列的作用是在需要处理具有不同优先级的元素集合时，能够方便地将优先级高的元素提取出来，以便优先处理。这在许多应用中都非常有用，例如：

1. 任务调度：在操作系统中，可以使用优先队列来调度不同优先级的任务，确保高优先级任务能够及时得到处理。

2. 最小（最大）值查找：优先队列常常用于查找集合中的最小（或最大）元素。例如，可以使用最小堆来实现一个优先队列，从而高效地找到最小的元素。

3. 图算法：在图算法中，优先队列可以帮助确定下一步的最优选择，如在Dijkstra算法中用于选择最短路径。

4. 合并有序序列：将多个有序序列合并成一个有序序列时，优先队列可以用于选择当前最小的元素，从而逐步构建有序序列。

5. 模拟系统：在某些模拟系统中，可以使用优先队列来模拟事件的发生顺序，以及根据事件的优先级来决定处理顺序。

总之，优先队列是一个非常有用的数据结构，它在许多场景中都能提供高效的解决方案，让程序能够更好地处理具有不同优先级的元素。

---

总结

普通的队列是先进先出，优先级队列不是先进先出，而是按优先级出。插入数据的时候，也是需要维护优先级，最终实现出的时候也是按优先级。

堆

怎么实现优先级队列？基于堆。

为什么要基于堆实现？

优先队列通常基于堆（heap）数据结构实现，是因为堆具有一些特性使其非常适合作为优先队列的底层数据结构。以下是基于堆实现优先队列的几个主要优势：

1. 高效的插入和删除操作：堆的插入和删除操作的时间复杂度都是 O(log n)，其中 n 是堆中元素的数量。这使得在优先队列中插入和删除元素的操作非常高效，适用于需要频繁更新队列的场景。

2. 维护元素顺序：堆是一种自我调整的数据结构，通过堆的调整操作，可以保证堆的根节点始终是最大（或最小）元素，从而满足了优先队列的要求。这样，无论何时需要取出最大（或最小）元素，都可以直接从根节点获取。

3. 稳定的性能：堆数据结构的性能与元素的数量关系不大，即使元素数量很大，插入和删除操作的时间复杂度也仍然是 O(log n)，这使得堆在处理大规模数据时依然能够保持高效。

4. 适应动态变化：堆适用于动态变化的情况，即在不断添加和删除元素的过程中，仍能保持相对稳定的性能。这在实际应用中很有用，例如任务调度、事件处理等场景。

5. 空间效率：相比其他数据结构，堆的实现相对紧凑，占用的额外内存较少，适用于内存有限的情况。

总之，基于堆实现的优先队列具有高效的插入和删除操作、维护元素顺序的能力以及适应动态变化的特点，这些特性使得堆非常适合用于构建优先队列，提供了在不同应用场景中处理优先级元素的便利性和高效性。

---

说白了，就是优先级这个东西，刚好和堆这个数据结构很像，因为堆每次出数据的时候，都是出根节点，堆的根节点的本质就是优先级高。

如何实现堆？

在Java中，堆可以通过数组来实现。有两种主要类型的堆：最大堆和最小堆。最大堆中父节点的值大于或等于其子节点的值，而最小堆中父节点的值小于或等于其子节点的值。下面是一个简单的基于数组的最小堆实现示例：

public class MinHeap {
    private int[] heapArray;
    private int maxSize;
    private int currentSize;

    public MinHeap(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        heapArray = new int[maxSize];
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public void insert(int value) {
        if (isFull()) {
            throw new IllegalStateException("Heap is full");
        }

        heapArray[currentSize] = value;
        trickleUp(currentSize);
        currentSize++;
    }

    private void trickleUp(int index) {
        int parentIndex = (index - 1) / 2;
        int valueToInsert = heapArray[index];

        while (index > 0 && heapArray[parentIndex] > valueToInsert) {
            heapArray[index] = heapArray[parentIndex];
            index = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }

        heapArray[index] = valueToInsert;
    }

    public int remove() {
        if (isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }

        int root = heapArray[0];
        heapArray[0] = heapArray[currentSize - 1];
        currentSize--;
        trickleDown(0);
        return root;
    }

    private void trickleDown(int index) {
        int smallerChildIndex;
        int valueToMove = heapArray[index];

        while (index < currentSize / 2) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;

            if (rightChildIndex < currentSize && heapArray[leftChildIndex] > heapArray[rightChildIndex]) {
                smallerChildIndex = rightChildIndex;
            } else {
                smallerChildIndex = leftChildIndex;
            }

            if (valueToMove <= heapArray[smallerChildIndex]) {
                break;
            }

            heapArray[index] = heapArray[smallerChildIndex];
            index = smallerChildIndex;
        }

        heapArray[index] = valueToMove;
    }
}

这个示例中，我们使用一个数组来实现最小堆。insert 方法用于插入新元素，会根据堆的特性将新元素逐步向上移动（trickle up）。remove 方法用于删除堆顶元素，会将最后一个元素移到堆顶，然后根据堆的特性将元素逐步向下移动（trickle down）。

请注意，这只是一个简单的最小堆实现示例，实际上，Java中的优先队列 PriorityQueue 类也是基于堆实现的。在使用堆时，需要仔细考虑细节，并确保实现的正确性和性能。

---

注意，可以基于数组来实现。也就是说，堆的基础数据结构是数组。同理，优先级队列的基础数据结构也是数组。

为什么要基于数组实现呢？优点是什么？

在实现堆的数据结构时，使用数组作为底层实现有一些优点，这些优点有助于提高性能和空间效率。以下是为什么要基于数组实现堆的一些主要优点：

1. 内存连续性：数组在内存中是连续存储的，这与堆的完全二叉树性质相匹配。这种内存布局使得访问数组中的元素更加高效，减少了因为跳跃式访问而带来的缓存不命中的情况。

2. 空间效率：相对于其他数据结构（如链表），数组具有较小的额外开销。在堆中，每个节点只需要一个数组元素来表示，不需要额外的指针或引用。

3. 直观索引关系：数组的索引关系可以直观地映射到堆的节点关系，例如，对于一个索引为 i 的节点，其左子节点位于 2i+1，右子节点位于 2i+2。这使得节点之间的关系更易于理解和处理。

4. 实现简单：基于数组的实现相对于基于链表等其他数据结构的实现来说，实现起来更加简单。这是因为不需要处理指针或引用，仅需要通过索引来访问元素。

5. 性能可预测性：数组实现的堆通常具有较好的性能可预测性。数组的存储和访问操作在大多数情况下都有较低的常数因子，从而使得性能更稳定。

6. 紧凑性：数组实现的堆通常相对紧凑，占用的内存空间较少，适用于内存有限的场景。

尽管基于数组的堆实现具有这些优点，也需要考虑一些缺点，比如在插入和删除元素时需要进行元素的移动和调整操作，这可能导致额外的性能开销。但总体而言，基于数组的堆实现在许多情况下都是非常高效和实用的选择。

堆是二叉树吗

是的，堆是一种特殊类型的二叉树。具体来说，堆通常被实现为一种二叉树数据结构，其中具有一些特定的性质，使其适合作为优先队列的底层数据结构。在堆中，每个节点都有一个值，而且满足以下两个性质：

1. 堆序性质（Heap Order Property）：在最大堆中，父节点的值大于或等于其子节点的值；在最小堆中，父节点的值小于或等于其子节点的值。

2. 完全二叉树性质（Complete Binary Tree Property）：堆通常被实现为完全二叉树，这意味着从根节点开始，每一层都会被填满，直到最后一层，最后一层的节点从左到右依次填入，没有缺失。

在堆中，通常使用数组来表示二叉树的结构。因为堆是完全二叉树，可以使用数组的索引来表示节点之间的关系。例如，对于一个最小堆，索引 0 处的元素是根节点，索引 i 处的元素的左子节点位于索引 2i+1 处，右子节点位于索引 2i+2 处。

需要注意的是，尽管堆是一种二叉树，但不同于一般的二叉搜索树（Binary Search Tree），堆并不强调节点之间的特定有序关系（除了堆序性质），而是专注于维护根节点的最大或最小值。这使得堆适用于高效地实现优先队列等数据结构。

源码分析

入队

示意图

源码

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Collection#add})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
public boolean add(E e) {
    return offer(e);
}

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
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;
}

出队

示意图

源码

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;
}

/**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

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;
}

小结

底层都是数组

/**
 * 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

peek和poll的区别

在Java的优先队列（PriorityQueue）中，peek() 和 poll() 都是用于获取队列中的元素，但它们之间有一些区别：

1. peek() 方法：

   • peek() 方法用于获取队列中的第一个元素（即队首元素）而不移除它。
   • 如果队列为空，peek() 方法会返回 null。
   • 该方法的时间复杂度为 O(1)，因为它只是返回队首元素，而不涉及移动元素。

2. poll() 方法：

   • poll() 方法用于获取队列中的第一个元素，并将其从队列中移除。
   • 如果队列为空，poll() 方法会返回 null。
   • 该方法的时间复杂度通常为 O(log n)，因为在移除元素后，需要进行堆的重新调整操作来维护堆的性质。

总之，peek() 用于查看队列中的第一个元素而不移除它，而 poll() 用于获取并移除队列中的第一个元素。在使用时，根据具体的需求选择合适的方法。如果你只想查看队列中的元素，使用 peek()；如果需要取出并处理队列中的元素，使用 poll()。

源码

public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

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;
}

官方文档

public class PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

基于优先级堆的无限优先级queue 。 优先级队列的元素根据它们的有序natural ordering ，或由一个Comparator在队列构造的时候提供，这取决于所使用的构造方法。 优先队列不允许null元素。 依靠自然排序的优先级队列也不允许插入不可比较的对象（这样做可能导致ClassCastException ）。

该队列的头部是相对于指定顺序的最小元素。 如果多个元素被绑定到最小值，那么头就是这些元素之一 - 关系被任意破坏。 队列检索操作poll ， remove ， peek和element访问在队列的头部的元件。

优先级队列是无限制的，但是具有管理用于在队列上存储元素的数组的大小的内部容量 。 它始终至少与队列大小一样大。 当元素被添加到优先级队列中时，其容量会自动增长。 没有规定增长政策的细节。

该类及其迭代器实现Collection和Iterator接口的所有可选方法。 方法iterator()中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。 如果需要有序遍历，请考虑使用Arrays.sort(pq.toArray()) 。

请注意，此实现不同步。  如果任何线程修改队列，多线程不应同时访问PriorityQueue实例。 而是使用线程安全的PriorityBlockingQueue类。

实现注意事项：此实现提供了O（日志（n））的时间入队和出队方法（ offer ， poll ， remove()和add ）; remove(Object)和contains(Object)方法的线性时间; 和恒定时间检索方法（ peek ， element和size ）。

这个班是Java Collections Framework的会员 。

总结

优先级队列是一种功能特殊的队列，不是先进先出，而是按优先级。

那怎么做到这一点呢？基于堆。因为堆的根节点就是最小或者最大数据，最小或最大的本质就是优先级。

那具体怎么实现堆呢？基于数组。

参考

《java高并发和集合框架》