Java 【数据结构】 优先级队列（PriorityQueue）和堆（Heap）【神装】

Java中的优先级队列（PriorityQueue）与堆（Heap）

优先级队列（PriorityQueue）和堆（Heap）都是在数据结构中非常重要的概念。优先级队列是一种特殊的数据结构，它的元素有优先级，元素的处理顺序依赖于其优先级而非插入顺序。而堆则是一种特殊的完全二叉树，它满足堆的性质，即每个节点都大于（或小于）其子节点。

一、优先级队列（PriorityQueue）

Java中的PriorityQueue类实现了优先级队列的特性。它使用堆数据结构来存储元素。默认情况下，PriorityQueue使用自然顺序来对元素进行排序，也可以通过提供一个比较器来自定义排序规则。

示例代码：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个优先级队列
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 添加元素
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(7);
        pq.offer(2);

        // 打印优先级队列中的元素
        System.out.println("优先级队列中的元素：");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 按优先级顺序移除并打印元素
        }
    }
}

在上述代码中，我们创建了一个PriorityQueue对象，并向其中添加了一些整数。由于默认是小根堆，输出的元素将按从小到大的顺序排列。

二、堆（Heap）

堆的实现通常分为最大堆（Max Heap）和最小堆（Min Heap）。最大堆的每个节点都大于或等于其子节点，而最小堆则相反。Java的PriorityQueue实际上就是基于最小堆的实现。

自定义堆的实现示例：

我们可以手动实现一个最大堆：

import java.util.Arrays;

class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素
    public void insert(int value) {
        if (size >= capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    // 向上堆化
    private void heapifyUp(int index) {
        int parentIndex;
        if (index != 0) {
            parentIndex = (index - 1) / 2;
            if (heap[index] > heap[parentIndex]) {
                swap(index, parentIndex);
                heapifyUp(parentIndex);
            }
        }
    }

    // 交换位置
    private void swap(int indexOne, int indexTwo) {
        int temp = heap[indexOne];
        heap[indexOne] = heap[indexTwo];
        heap[indexTwo] = temp;
    }

    // 移除堆顶元素
    public int remove() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int removedValue = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return removedValue;
    }

    // 向下堆化
    private void heapifyDown(int index) {
        int largest = index;
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;

        if (leftChildIndex < size && heap[leftChildIndex] > heap[largest]) {
            largest = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] > heap[largest]) {
            largest = rightChildIndex;
        }
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }

    // 打印堆
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }
}

public class HeapExample {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(3);
        maxHeap.insert(10);
        maxHeap.insert(5);
        maxHeap.insert(1);

        System.out.println("当前堆状态：");
        maxHeap.printHeap();

        System.out.println("移除堆顶部元素：" + maxHeap.remove());

        System.out.println("移除后的堆状态：");
        maxHeap.printHeap();
    }
}

在这个示例中，我们手动实现了一个最大堆，并提供了插入和移除元素的功能。insert方法会在堆中插入新的元素，并通过heapifyUp方法维持堆的性质。remove方法则移除堆顶元素，并通过heapifyDown方法重建堆的结构。

结论

Java的PriorityQueue实现了优先级队列的特性，并基于堆的原理。利用堆的特性，我们能够高效地实现如任务调度、数据排序等功能。理解优先级队列和堆的概念，对于提高算法效率和优化代码性能都是非常关键的。