数据结构（Java）：优先级队列(堆)&堆的模拟实现&PriorityQueue集合

在Java中，PriorityQueue是一个基于优先级堆的无界队列，元素按照其自然顺序进行排序，或者根据提供的Comparator进行排序。以下是PriorityQueue的一个简单模拟实现：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
 
public class MyPriorityQueue<T> {
    private List<T> heap;
    private Comparator<T> comparator;
 
    public MyPriorityQueue() {
        this(Comparator.naturalOrder());
    }
 
    public MyPriorityQueue(Comparator<T> comparator) {
        this.comparator = comparator;
        this.heap = new ArrayList<>();
    }
 
    private void up(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (comparator.compare(heap.get(parent), heap.get(index)) <= 0) {
                break;
            }
            T temp = heap.get(parent);
            heap.set(parent, heap.get(index));
            heap.set(index, temp);
            index = parent;
        }
    }
 
    private void down(int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int smaller = left + 1 < size && comparator.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
            smaller = comparator.compare(heap.get(smaller), heap.get(index)) < 0 ? smaller : index;
            if (smaller == index) {
                break;
            }
            T temp = heap.get(smaller);
            heap.set(smaller, heap.get(index));
            heap.set(index, temp);
            index = smaller;
            left = index * 2 + 1;
        }
    }
 
    public void offer(T element) {
        heap.add(element);
        up(heap.size() - 1);
    }
 
    public T poll() {
        if (heap.isEmpty()) {
            return null;
        }
        T min = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        down(0, heap.size());
        return min;
    }
 
    public T peek() {
        return heap.isEmpty() ? null : heap.get(0);
    }
}

这个模拟的MyPriorityQueue类提供了offer方法来添加元素，poll方法来移除并返回队列顶部的最小元素，peek方法来返回最小元素但不移除它。up和down方法分别用于保持堆的属性，即子节点小于（或等于）其父节点。

使用示例：

MyPriorityQueue<Integer> myQueue = new MyPriorityQueue<>();
myQueue.offer(3);
myQueue.offer(1);