Java 数据结构篇-用数组、堆实现优先级队列

在Java中，可以使用数组或者堆（如最大堆或最小堆）来实现优先级队列。以下是使用数组和堆实现优先级队列的示例代码。

使用数组实现：

public class PriorityQueue {
    private int[] heap;
    private int size;
 
    public PriorityQueue(int capacity) {
        this.heap = new int[capacity];
        this.size = 0;
    }
 
    public void insert(int element) {
        if (size == heap.length) {
            // 数组满了，需要扩容
            throw new RuntimeException("Priority queue is full.");
        }
        heap[size] = element;
        siftUp(size);
        size++;
    }
 
    public int extractMax() {
        if (isEmpty()) {
            throw new RuntimeException("Priority queue is empty.");
        }
        int max = heap[0];
        swap(0, size - 1);
        size--;
        siftDown(0);
        return max;
    }
 
    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] >= heap[index]) {
                break;
            }
            swap(index, parent);
            index = parent;
        }
    }
 
    private void siftDown(int index) {
        int left = index * 2 + 1;
        while (left < size) {
            // 找到子节点中较大的一个
            int largest = (left + 1 < size && heap[left + 1] > heap[left]) ? left + 1 : left;
            largest = heap[largest] > heap[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
 
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
}

使用堆实现：

import java.util.PriorityQueue;
 
public class PriorityQueue {
    private java.util.PriorityQueue<Integer> queue;
 
    public PriorityQueue() {
        this.queue = new PriorityQueue<>();
    }
 
    public void insert(int element) {
        queue.offer(element);
    }
 
    public int extractMax() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Priority queue is empty.");
        }
        return queue.poll();
    }
 
    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

在数组实现中，siftUp 和 siftDown 方法用于维护堆的性质。在堆实现中，PriorityQueue 类是Java标准库提供的，它已经内部维护了堆的性质。