# Data Structure / Heap & Priority Queue

## 第一章：認識堆積（Heap）

### 1.1 什麼是堆積？

在開始學習堆積之前，讓我們先回想一下我們已經認識的樹狀結構。一般的二元樹（Binary Tree）允許每個節點有最多兩個子節點，但節點之間的值並沒有特定的順序關係。而堆積則是一種特殊的完整二元樹，它不僅有結構上的要求，還要求節點之間必須符合特定的順序關係。

堆積具有兩個重要的特性：

1. **結構特性：完整二元樹（Complete Binary Tree）**
- 除了最後一層外，所有層級都必須從左到右填滿
- 最後一層的節點必須靠左填充
- 這個特性讓我們能夠使用陣列來有效地儲存堆積
2. **順序特性：節點之間存在特定的大小關係**
- 最小堆積（Min Heap）：父節點永遠小於或等於其子節點
- 最大堆積（Max Heap）：父節點永遠大於或等於其子節點

讓我們用視覺化的方式來理解這些概念（順邊跟大家炫耀我新學的酷東東）：

### 1.2 為什麼需要堆積？

堆積的設計特性使它特別適合用於需要頻繁找出最大值或最小值的場景。想像以下情境：

1. 作業系統的工作排程：優先級最高的工作需要最先執行
2. 遊戲的分數排行榜：需要即時維護最高分
3. 網路封包的優先級處理：緊急封包需要優先處理

在這些情況下，如果使用一般的陣列或鏈結串列，要找出最大值或最小值就需要遍歷整個資料結構，時間複雜度為 $O(n)$。但使用堆積，我們可以在 $O(1)$ 的常數時間內取得最大值或最小值，這就是堆積的優勢所在。

### 1.3 堆積的基本實作

#### 1.3.1 MaxHeap 類別（Array Base）

class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;
    
    // constructor：初始化堆積
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }
    
    // helpers：取得父節點的索引
    private int parent(int index) {
        return (index - 1) / 2;
    }
    
    // helpers：取得左子節點的索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    
    // helpers：取得右子節點的索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    
    // helpers：交換兩個節點的值
    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

#### 1.3.2 核心操作：插入（insert）和取出最大值（extractMax）。

class MaxHeap {
    // ... 樓上的程式碼 ...
    
    // 插入新元素
    public void insert(int value) {
        if (size >= capacity) {
            throw new IllegalStateException("堆積已滿");
        }
        
        // 步驟 1：將新元素放在最後一個位置
        heap[size] = value;
        
        // 步驟 2：向上調整（維護堆積性質）
        heapifyUp(size);
        
        size++;
    }
    
    // 向上調整的輔助方法
    private void heapifyUp(int index) {
        // 只要還沒到根節點，且目前節點大於父節點
        while (index > 0 && heap[index] > heap[parent(index)]) {
            // 交換目前節點與父節點
            swap(index, parent(index));
            // 移動到父節點位置，繼續檢查
            index = parent(index);
        }
    }
    
    // 取出最大值
    public int extractMax() {
        if (size <= 0) {
            throw new IllegalStateException("堆積為空");
        }
        
        // 步驟 1：儲存最大值（根節點）
        int maxValue = heap[0];
        
        // 步驟 2：將最後一個元素移到根節點
        heap[0] = heap[size - 1];
        size--;
        
        // 步驟 3：向下調整（維護堆積性質）
        heapifyDown(0);
        
        return maxValue;
    }
    
    // 向下調整的輔助方法
    private void heapifyDown(int index) {
        int maxIndex = index;
        int leftIndex = leftChild(index);
        int rightIndex = rightChild(index);
        
        // 比較左子節點
        if (leftIndex < size && heap[leftIndex] > heap[maxIndex]) {
            maxIndex = leftIndex;
        }
        
        // 比較右子節點
        if (rightIndex < size && heap[rightIndex] > heap[maxIndex]) {
            maxIndex = rightIndex;
        }
        
        // 如果找到更大的子節點，就交換並繼續向下調整
        if (maxIndex != index) {
            swap(index, maxIndex);
            heapifyDown(maxIndex);
        }
    }
    
    // 查看最大值（不移除）
    public int peekMax() {
        if (size <= 0) {
            throw new IllegalStateException("堆積為空");
        }
        return heap[0];
    }
}

#### 1.3.3 Demo

public class HeapExample {
    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(10);
        
        // 插入一些數值
        heap.insert(45);
        heap.insert(20);
        heap.insert(60);
        heap.insert(35);
        heap.insert(75);
        heap.insert(30);
        
        // 依序取出最大值
        System.out.println("\n取出的順序：");
        while (heap.getSize() > 0) {
            System.out.print(heap.extractMax() + " ");
        }
        // 輸出結果：75 60 45 35 30 20
    }
}

執行這段程式碼時，我們可以發現堆積會自動將最大的數值移到頂端，並且在取出時永遠能得到當前最大的數值。

## 第二章：優先佇列（Priority Queue）

### 2.1 什麼是優先佇列？

優先佇列是一種特殊的佇列，它的特點是元素的出佇順序是根據優先級來決定的，而不是先進先出（FIFO）。**在實際應用中，優先佇列通常使用堆積來實作，因為堆積的特性非常適合維護優先級關係。**

### 2.2 優先佇列的基礎實作

呱呱醫院急診室正在建立一個病患分類系統，讓我們用 PQ 實作：

#### 2.2.1 Patient 類別

class Patient implements Comparable<Patient> {
    private String name;
    private int priority;  // 優先級：1=危急 2=緊急 3=次緊急 4=非緊急
    private long arrivalTime;  // 到達時間（用於相同優先級的排序）
    
    public Patient(String name, int priority) {
        this.name = name;
        this.priority = priority;
        this.arrivalTime = System.currentTimeMillis();
    }
    
    @Override
    public int compareTo(Patient other) {
        // 先比較優先級
        if (this.priority != other.priority) {
            return this.priority - other.priority;
        }
        // 優先級相同時，比較到達時間
        return Long.compare(this.arrivalTime, other.arrivalTime);
    }
    
    @Override
    public String toString() {
        return String.format("病患：%s (優先級：%d)", name, priority);
    }
}

#### 2.2.2 EmergencyRoom 類別

public class EmergencyRoom {
    private PriorityQueue<Patient> waitingList;
    
    public EmergencyRoom() {
        // Java 內建的 PriorityQueue 預設是最小堆積
        // 所以優先級數字越小代表越優先
        this.waitingList = new PriorityQueue<>();
    }
    
    public void addPatient(String name, int priority) {
        Patient patient = new Patient(name, priority);
        waitingList.offer(patient);
        System.out.printf("新病患加入候診：%s%n", patient);
    }
    
    public void treatNextPatient() {
        if (waitingList.isEmpty()) {
            System.out.println("目前沒有待診病患");
            return;
        }
        
        Patient patient = waitingList.poll();
        System.out.printf("正在診治：%s%n", patient);
    }
    
    public void showWaitingList() {
        if (waitingList.isEmpty()) {
            System.out.println("候診清單為空");
            return;
        }
        
        System.out.println("\n目前候診清單 (僅代表優先佇列中的內容)：");
        // 注意：這種方式只是用來展示，並不代表優先佇列 deque 的順序
        waitingList.forEach(System.out::println);
        System.out.println();

        System.out.println("目前候診清單 (排序過後的內容 & deque 的順序)：");
        List<Patient> sortedList = new ArrayList<>(waitingList);
        Collections.sort(sortedList);
        sortedList.forEach(System.out::println);
        System.out.println();
    }
}

#### 2.2.3 Demo

public class EmergencyRoomDemo {
    public static void main(String[] args) {
        EmergencyRoom er = new EmergencyRoom();
        
        // 模擬病患陸續到達急診室
        er.addPatient("王小明", 3);  // 次緊急
        er.addPatient("李大華", 1);  // 危急
        er.addPatient("張三", 4);    // 非緊急
        er.addPatient("陳小玉", 2);  // 緊急
        er.addPatient("林志明", 1);  // 危急
        
        er.showWaitingList();
        
        // 模擬醫生依序診治病患
        System.out.println("開始診治病患：");
        for (int i = 0; i < 3; i++) {
            er.treatNextPatient();
        }
        
        er.showWaitingList();
    }
}

### 2.3 優先序列的特點

1. 自動排序：不需要手動維護順序，堆積會自動將最高優先級的元素移到最前面。
2. 動態調整：可以隨時加入新的元素，系統會自動調整順序。
3. 效能優勢：
- 取得最高優先級元素：$O(1)$
- 新增元素：$O(\log n)$
- 移除最高優先級元素：$O(\log n)$

優先佇列的其他實際應用場景還有**網路路由器的封包處理**、**作業系統的工作排程**或**遊戲引擎的事件處理**。透過將問題抽象化為優先級的概念，我們可以利用堆積的特性來有效地管理和處理這些需要按照特定順序處理的資料。

## 第三章：堆積排序（Heap Sort）

### 3.1 什麼是堆積排序

堆積排序是一種利用堆積特性來進行排序的演算法。它的基本思想是先將資料建立成一個最大堆積，然後反覆取出堆頂的最大值，並重新調整堆積結構。


### 3.2 堆積排序的基本實作

#### 3.2.1 HeapSort 類別

class HeapSort {
    public void sort(int[] arr) {
        int n = arr.length;
        
        // 第一階段：建立最大堆積
        // 從最後一個非葉節點開始，依序進行堆積調整
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 第二階段：依序取出最大值
        for (int i = n - 1; i > 0; i--) {
            // 將堆頂（最大值）與最後一個元素交換
            swap(arr, 0, i);
            
            // 對根節點進行堆積調整，重建最大堆積
            heapify(arr, i, 0);
        }
    }
    
    /**
     * 堆積調整函數
     * @param arr 要調整的陣列
     * @param n 目前堆積的大小
     * @param i 要調整的節點索引
     */
    private void heapify(int[] arr, int n, int i) {
        int largest = i;  // 假設目前節點是最大值
        int left = 2 * i + 1;  // 左子節點
        int right = 2 * i + 2;  // 右子節點
        
        // 如果左子節點大於目前最大值
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子節點大於目前最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大值不是目前節點，進行交換並遞迴調整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

#### 3.2.2 Demo

public class HeapSortDemo {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        HeapSort heapSort = new HeapSort();
        
        System.out.println("原始陣列：");
        printArray(arr);
        
        heapSort.sort(arr);
        
        System.out.println("排序後陣列：");
        printArray(arr);
    }
    
    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

## 第四章：建堆過程（Heapify Process）的詳細解析

### 4.1 理解堆積建構過程

在開始介紹程式碼實作之前，我們需要理解建堆的兩個重要概念：

1. 為什麼要從最後一個非葉節點開始？
- 葉節點本身已經符合堆積性質
- 最後一個非葉節點的位置是 **`(n/2)-1`**
- 由下而上處理可以確保子樹都已經是堆積
2. 調整過程的核心思想：
- 將當前節點與其子節點比較
- 確保父節點永遠大於（最大堆）或小於（最小堆）其子節點
- 如果需要交換，則可能影響下層結構，需要繼續向下調整

### 4.2 程式碼實作

#### 4.2.1 MaxHeapBuilder 類別

class MaxHeapBuilder {
    /**
     * 將一個普通陣列轉換成最大堆積
     * @param arr 待轉換的陣列
     */
    public static void buildMaxHeap(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        
        int lastNonLeafNode = (arr.length / 2) - 1;
        
        // 從最後一個非葉節點開始，逐一向上處理每個節點
        for (int i = lastNonLeafNode; i >= 0; i--) {
            siftDown(arr, arr.length, i);
        }
    }
    
    /**
     * 將指定節點向下調整到適當位置，確保最大堆積性質
     * @param arr 陣列
     * @param heapSize 目前堆積的有效大小
     * @param root 當前要調整的節點索引
     */
    private static void heapifyDown(int[] arr, int heapSize, int root) {
        while (true) {
            int maxIndex = root;
            int leftChild = 2 * root + 1;
            int rightChild = 2 * root + 2;
            
            // 找出根節點、左子節點和右子節點中的最大值
            if (leftChild < heapSize && arr[leftChild] > arr[maxIndex]) {
                maxIndex = leftChild;
            }
            if (rightChild < heapSize && arr[rightChild] > arr[maxIndex]) {
                maxIndex = rightChild;
            }
            
            // 如果根節點已經是最大的，表示這個子樹已經符合堆積性質
            if (maxIndex == root) {
                break;
            }
            
            // 交換節點值並繼續調整被影響的子樹
            swap(arr, root, maxIndex);
            root = maxIndex;
        }
    }
    
    // 交換陣列中兩個元素的值
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    /**
     * 以樹狀結構視覺化顯示堆積內容
     * @param arr 要顯示的堆積陣列
     */
    public static void visualizeHeap(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("空堆積");
            return;
        }
        
        int maxLevel = (int) Math.ceil(Math.log(arr.length + 1) / Math.log(2));
        int maxWidth = (int) Math.pow(2, maxLevel - 1) * 3;
        
        for (int level = 0; level < maxLevel; level++) {
            int startIndex = (int) Math.pow(2, level) - 1;
            int nodesInLevel = (int) Math.pow(2, level);
            int spacing = maxWidth / (nodesInLevel + 1);
            
            // 印出當前層級的節點
            for (int i = 0; i < nodesInLevel && startIndex + i < arr.length; i++) {
                System.out.print(String.format("%" + spacing + "s", arr[startIndex + i]));
            }
            System.out.println();
        }
    }
}

#### 4.2.2 Demo

public class HeapBuildingDemo {
    public static void main(String[] args) {
        // 準備測試資料
        int[] arr = { 4, 10, 3, 5, 1, 2, 8, 7, 6, 9 };

        System.out.println("原始陣列：");
        System.out.println(Arrays.toString(arr));
        System.out.println("\n原始的樹狀結構：");
        MaxHeapBuilder.visualizeHeap(arr);

        // 建立最大堆積
        MaxHeapBuilder.buildMaxHeap(arr);

        System.out.println("\n建堆後的陣列：");
        System.out.println(Arrays.toString(arr));
        System.out.println("\n最終的最大堆積結構：");
        MaxHeapBuilder.visualizeHeap(arr);

        // 驗證堆積性質
        System.out.println("\n驗證結果：" +
                (isValidMaxHeap(arr, 0) ? "是有效的最大堆積" : "不是有效的最大堆積"));
    }

    // 驗證是否為有效的最大堆積
    private static boolean isValidMaxHeap(int[] arr, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 檢查左子節點
        if (left < arr.length) {
            if (arr[i] < arr[left] || !isValidMaxHeap(arr, left)) {
                return false;
            }
        }

        // 檢查右子節點
        if (right < arr.length) {
            if (arr[i] < arr[right] || !isValidMaxHeap(arr, right)) {
                return false;
            }
        }

        return true;
    }
}

### 4.4 效能分析
1. **時間複雜度：**
- 表面的分析：每個節點最多需要向下調整 $\log n$ 層，共有 $n/2$ 個非葉節點
- 因此看似是 $O(n \log n)$
- 但實際上，越靠近根節點的節點越少，且需要調整的層數越多
- 透過 Master Theorem 可以證明實際複雜度為 $O(n)$
2. **空間複雜度：**
- 遞迴調用的堆疊深度最大為 $O(\log n)$
- 整體空間複雜度為 $O(1)$
3. **實務應用考量：**
- 對於小型資料集，建堆方式的選擇影響不大
- 對於大型資料集，向上調整的方法明顯更優
- 如果需要動態維護堆積，可能需要同時實作向上調整（heapifyUp）操作