Java大頂堆詳解

一、大頂堆概述

大頂堆（Max Heap）是一種完全二叉樹，其中任何一顆子樹的根節點都大於等於其子節點。大頂堆通常用於實現優先隊列和堆排序。

大頂堆的基本操作包括插入元素、刪除堆頂元素、堆排序等。在Java中，可以通過PriorityQueue類來實現大頂堆的基本操作。

二、PriorityQueue類詳解

PriorityQueue類是Java集合框架中的一個類，它實現了Queue介面，可以實現隊列的基本操作，如添加、刪除、查看隊列頭部元素等。

與普通隊列不同的是，PriorityQueue類默認實現了大頂堆（即插入元素時自動按照元素大小排序），因此可以很方便地實現基於優先順序的排序。

以下是PriorityQueue類的一些常用方法：

public boolean add(E e) //添加元素，若添加成功則返回true，否則拋出異常
public E remove() //刪除堆頂元素並返回其值，若堆為空則拋出異常
public E peek() //返回堆頂元素的值，若堆為空則返回null
public int size() //返回堆中元素的個數

三、插入元素

在PriorityQueue中，插入元素時會自動按照元素大小排序。因此，只需要調用add()方法即可完成插入操作。

以下是插入元素的示例代碼：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(15);

//輸出堆中的元素
while (!maxHeap.isEmpty()) {
    System.out.print(maxHeap.poll() + " ");
}
//輸出結果為20 15 10

在上述代碼中，我們創建了一個大頂堆，插入了三個元素10、20、15。由於使用了Collections.reverseOrder()，因此PriorityQueue會自動按照降序排列元素。在輸出時，我們使用了poll()方法來逐個彈出堆頂元素。

四、刪除堆頂元素

在PriorityQueue中，刪除堆頂元素是指刪除堆中優先順序最高的元素（即堆頂元素）。常用的方法是remove()。

以下是刪除堆頂元素的示例代碼：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(15);

maxHeap.remove();

//輸出堆中的元素
while (!maxHeap.isEmpty()) {
    System.out.print(maxHeap.poll() + " ");
}
//輸出結果為15 10

在上述代碼中，我們創建了一個大頂堆，並插入了三個元素10、20、15。刪除堆頂元素後，我們仍然使用了poll()方法來輸出堆中的剩餘元素。

五、堆排序

堆排序是利用大頂堆排序的一種演算法，其基本思想是藉助大頂堆快速找到最大元素，並將其放到待排數組的末尾；然後將剩餘元素重新構建大頂堆，重複上述操作。

以下是堆排序的示例代碼：

public static void heapSort(int[] nums) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int i = 0; i < nums.length; i++) {
        maxHeap.add(nums[i]);
    }
    for (int i = 0; i < nums.length; i++) {
        nums[i] = maxHeap.poll();
    }
}

//測試代碼
int[] nums = { 4, 2, 7, 1, 3 };
heapSort(nums);
System.out.println(Arrays.toString(nums));
//輸出結果為[7, 4, 3, 2, 1]

在上述代碼中，我們使用PriorityQueue來構建大頂堆，並將待排數組中的元素依次插入。然後，通過多次使用poll()方法，逐個取出堆中的元素，並將其重新賦值給待排數組，最終實現了堆排序的目的。