Priorityqueue最大堆

在計算機科學中，優先佇列（Priority Queue）是一種數據結構，其中元素按照優先權進行排序。優先佇列允許我們高效地插入新元素和刪除具有最高優先權的元素。優先佇列通常使用堆（Heap）來實現，堆是一種特殊的完全二叉樹，可以分為最大堆和最小堆兩種。

最大堆（Max-Heap）是一種堆，其中每個節點的值都不小於其子節點的值。在最大堆中，根節點是最大值。最大堆可以用來實現優先佇列，使得我們可以通過O(log n)的時間複雜度來插入新元素和刪除最大元素。

下面是使用最大堆實現優先佇列的基本步驟：

1. 初始化一個空的堆。
2. 插入新元素時，將新元素添加到堆的底部，然後通過向上調整（Heapify-Up）操作，將新元素移動到正確的位置，直到它滿足堆的性質。
3. 刪除最大元素時，直接刪除根節點，然後將最後一個元素放到根節點的位置，然後通過向下調整（Heapify-Down）操作，將堆的根節點移動到正確的位置，直到它滿足堆的性質。

最大堆和最小堆的區別在於堆頂元素的特性：最大堆的堆頂元素是整個堆中最大的元素，而最小堆的堆頂元素是最小的元素。

在Java中，有一個內置的優先佇列類PriorityQueue，它是使用最小堆實現的。如果你需要最大堆，你可以通過在PriorityQueue中使用自定義的比較器來實現，該比較器將元素按照相反的順序進行排序，即最大的元素排在最前面。

下面是一個簡單的示例，展示了如何使用PriorityQueue來實現最大堆：

import java.util.Comparator;
import java.util.PriorityQueue;

public class MaxHeapUsingPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; // 使用相反的順序進行排序
            }
        });

        maxHeap.offer(10);
        maxHeap.offer(5);
        maxHeap.offer(15);
        maxHeap.offer(2);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 刪除最大元素
        }
    }
}

在這個例子中，我們創建了一個PriorityQueue，並提供了一個比較器，該比較器將元素按照相反的順序進行排序，這樣PriorityQueue就變成了一個最大堆。然後我們向堆中添加了一些元素，並循環刪除最大元素。

請注意，Java的PriorityQueue實現的是最小堆，而不是最大堆，因此我們需要提供一個自定義的比較器來達到最大堆的效果。