純數據結構Java實現(6/11)(二叉堆&優先隊列)
- 2019 年 10 月 3 日
- 筆記
堆其實也是樹結構(或者說基於樹結構)，一般可以用堆實現優先隊列。
二叉堆
堆可以用於實現其他高層數據結構，比如優先隊列
而要實現一個堆，可以藉助二叉樹，其實現稱為: 二叉堆 (使用二叉樹表示的堆)。
但是二叉堆，需要滿足一些特殊性質:
其一、二叉堆一定是一棵完全二叉樹 (完全二叉樹可以用數組表示，見下面)
完全二叉樹缺失的部分一定是在右下方。(每層一定是從左到右的順序優先存放)
- 完全二叉樹的結構，可以簡單理解成按層安放元素的。(所以數組是不錯的底層實現)
其二、父節點一定比子節點大 (針對大頂堆的情況)。
二叉堆實現
因為二叉堆是完全二叉樹，又因為完全二叉樹可以用數組的方式實現
(數組編號/索引，正好對應數組的索引/下標)
故而這裡完全二叉樹的實現就可以繞過二叉樹的定義(不用使用 left, right 這樣的定義)。
這樣表示的好處是可以根據索引來判斷父子關係(而不用 left, right關係):
具體關係，可以用數學歸納法證明。
注意一下，0 這個位置要空出來，如果從 0 開始存儲的話，規律是這樣的:
數組實現:
基本的框架很簡單，大致如下:
package maxheap; import array.AdvanceDynamicArray; public class MaxHeap<E extends Comparable<E>> { //用動態數組進行實現 private AdvanceDynamicArray<E> data; //構造函數 public MaxHeap(int capacity) { data = new AdvanceDynamicArray<>(capacity); } public MaxHeap() { data = new AdvanceDynamicArray<>(); } //2個簡單的方法 public int getSize() { return data.getSize(); } public boolean isEmpty() { return data.isEmpty(); } //三個輔助函數，根據索引計算父，子存儲位置索引 private int parent(int index) { if (index == 0) { //根索引沒有父親 throw new IllegalArgumentException("index 0 沒有父親節點"); } return (index - 1) / 2; } private int leftChild(int index) { return index * 2 + 1; } private int rightChild(int index) { return index * 2 + 2; } //存取元素 //外部的 add，對於堆來說就是 sift up (上浮) }但是增刪的時候，涉及到重新調整樹結構，需要分析一下。
直接說結論: 先添加，後調整。
首先、只是放上去存儲，則比較簡單，見下圖:
- 樹的視角，本層放的下，則放在本層(從左至右的末尾)；本層放不下，那麼就放在下一層。
- 數組的角度，就是放在index末尾，圖上就是 index 為 10 的地方。
但是放上去還沒有完。
其次、一般還要進行相關的調整，否則不滿足二叉堆的第二個性質: 父節點大於子節點。
怎麼調整？上浮。
即、只需要調整新節點的父節點，父節點的父節點。。。這一條線上的父節點即可。
(這裡最後一次和根節點比較，不用交換)
也就是說，總共過程就兩個:
- 1.末尾添加
- 2.不停的交換，直到不再大於其父節點
程式碼如下(就是一個循環替換，比較的過程):
//外部的 add，對於堆來說就是 sift up (上浮) public void add(E e) { data.append(e); //先向數組末尾添加元素 //維護上浮 (隊數組進行交換) siftUp(data.getSize()-1); } private void siftUp(int index) { //給定 index 的元素不斷和父節點比較 while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) { //父節點比子節點小，交換 (上浮) data.swap(parent(index), index); //然後再向上找 index = parent(index); } }刪除元素(取出元素):
這裡的取出元素比較特殊，為了保證堆的高效，一般定義只能取出頂部的元素。
拿走堆頂的元素固然簡單，但是剩餘的兩顆子樹就要進行融合，過程就複雜了。
直接說結論: 摘頂之後，先上浮末尾元素，然後調整(下沉)合適位置。
(也就是說，末尾元素替換/覆蓋頂部元素，然後 sift down 調整)
舉個例子:
替換/覆蓋後:
然後，此時看到，並沒有歸為合適的位置。需要下沉。
如何下沉，每次和它的兩個孩子中最大的元素進行交換(因為大頂堆一定是根最大)。
什麼時候終止: 當前節點 >= 其兩個子節點(前提是其存在子節點)。
(葉子節點，沒有子節點，不需要調整了)
簡單實現:
public E findMax() { if (isEmpty()) { throw new IllegalArgumentException("這是個空堆"); } return data.get(0); } public E extractMax() { E ret = findMax(); data.swap(0, getSize() - 1); //覆蓋堆頂元素 data.pop(); //刪除末尾的元素 siftDown(0); //只下沉根元素下浮調整 return ret; } private void siftDown(int index) { //1.葉子節點時不用再交換了(數組越界了，說明其就是葉子節點了) //2.當前節點還是小於 `max(其子節點)` //有左孩子，內部再檢查有無有孩子 while (leftChild(index) < getSize()) { //找到孩子中的大的一個 (三個元素中找最大，順便交換) int maxIndex = leftChild(index); //默認先認為左變大 //如果右孩子存在，那就和右邊比一下 int rightIndex = rightChild(index); if (rightIndex < getSize() && data.get(rightIndex).compareTo(data.get(maxIndex)) > 0) { //說明確實右邊大 maxIndex = rightIndex; } //此時 maxIndex 就代表了孩子中大的一方的索引 if (data.get(index).compareTo(data.get(maxIndex)) >= 0) { break; //不用比了，已經是大頂堆了 } data.swap(index, maxIndex); index = maxIndex; //接著進行下一輪比較 } }測試一下放入 100 個數據，然後不斷的拿出大的來，放入數組，最後檢查這個數組是否是降序的。有點類似堆排序 (但藉助了額外的數組):
public static void main(String[] args) { int n = 1000000; //100萬 MaxHeap<Integer> maxHeap = new MaxHeap<>(); Random random = new Random(); //放入堆中 (需要不斷的 sift up) for(int i = 0; i < n; i++) { maxHeap.add(random.nextInt(Integer.MAX_VALUE)); } //然後取出來放入 arr 中 int[] arr = new int[n]; for(int i = 0; i< n; i++) { arr[i] = maxHeap.extractMax(); } //檢查一下這個 arr 是否是降序的 for(int i = 1; i< n; i++) { if(arr[i-1] < arr[i]) { //說明不是降序的，堆實現有問題 throw new IllegalArgumentException("Error"); } } //全部檢查完畢還沒有異常，就說明 OK System.out.println("OK"); }複雜度分析
主要分析 add 和 extractMax, 其實還是 O(logn)，因為交換的層級是高度 h，即 logn(因為是完全二叉樹)。
但是構建或者說存儲一棵大頂堆，複雜度是 O(nlogn)。
構建大頂堆的優化
上面已經說了，構建一個大頂堆，需要 O(nlogn)，如何優化？
heapify優化(任意數組整理成堆的存儲)。
直接說結論，用 sift down 替代 add 構建大頂堆
上面的 add 方法，慢慢構建一個大頂堆，步驟如下:
- 添加到末尾
- 慢慢 sift up 調整
這裡有一個非常重要的默認思想，那就是，一個元素一個元素的放入數組，慢慢構建大頂堆。
如果，現在假定存儲的數組就是一棵完全二叉樹(意思是，按照完全二叉樹那樣子，進行編號)，舉個例子，見下圖:
(只是完全二叉樹，但並不能稱為堆)
然後葉子節點先不管(因為葉子節點沒有孩子，而後面要進行 sift down 下沉操作，需要孩子節點)，對所有的非葉子節點進行 sift down。從第一個非葉子節點向根節點走(也就是數組末端開始)，圖:
- 數組最大索引處可以定位第一個非葉子節點(
getSize()-1)的 parent - 最後一層的葉子節點，可以忽略 (這樣至少減少了一半的工作量) — 這是關鍵
- siftDown方法裡面就包含了對葉子的過濾，即只對非葉子節點進行siftDown
這麼一來其實就很簡單了，大概的複雜度也就是 O(n)，比一個個添加(O(n*logN))的好處在於，上來就拋棄了所有的葉子節點，這個將近減少了一半的工作量。(實際減少的數目可以根據最大索引計算)
簡單實現如下(對著數組看即可):
public MaxHeap(E[] arr) { data = new AdvanceDynamicArray<>(arr); //把數組折騰成大頂堆 for (int i = parent(getSize() - 1); i >= 0; i--) { siftDown(i); } }其實在大數量級下， n 和 nlongn 近乎一致，相差不了太多。(雖然是不同的數量級)
(再次注意: 這裡的 heapify 的時間複雜度是 O(n) 級別。)
優先隊列
構建優先隊列不一定要用堆，但是底層用堆實現效率比較高
- 普通隊列: 先進先出，後進後出
- 出隊順序和入隊順序無關，只和優先順序有關(出隊的時候要看)
隨時根據新入隊的元素調整優先順序:
- 優先順序的意義可以自己定義，比如每次值最大的元素先出隊
- 優先順序，一般都是作用於出隊上
介面定義
因為優先隊列也是隊列，所以介面還是 Queue，即:
interface Queue<E> { void enqueue(E); E dequeue(); //拿到優先順序最高的元素 E getFront(); //拿到優先順序最高的元素 int getSize(); boolean isEmpty(); }堆實現
用線性結構，此時不論是有序線性結構還是無序線性結構，入隊和出隊總是保持在 O(1),O(n); 如果用 BST 實現的話，它最好的情況保持在 O(logn)，但最壞的情況可能會退化到 O(n)。
堆可以保證，在最差的情況都是 O(logn) 水平。
也就是說，在 PrioryQueue 內部封裝一個堆即可。(堆兼容所有的隊列介面)
程式碼試下如下:
package maxheap; import queque.Queue; public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { //內部成員 private MaxHeap<E> maxHeap; //構造函數 public PriorityQueue() { maxHeap = new MaxHeap<>(); } @Override public boolean isEmpty() { return maxHeap.isEmpty(); } @Override public int getSize() { return maxHeap.getSize(); } @Override public E dequeue() { return maxHeap.extractMax(); // 已經對空的情況做了處理 } @Override public E getFront() { //獲取優先順序最大的元素 return maxHeap.findMax(); //已經對空的情況作了處理 } @Override public void enqueue(E o) { maxHeap.add(o); } }Java中的優先隊列
重新整理一下，Java中的優先隊列
Java 的 PriorityQueue 是最小堆(頂部始終存儲的是優先順序最低的)。
但是小頂堆是默認存儲優先順序最低的元素，但優先順序是自己定義的，所以當你反寫 compareTo 或者比較器時，那麼即便是小頂堆，那麼實際上存儲還是大頂堆的方式。(堆頂拿到的也就是優先順序最大的元素)
這裡應用就太多了，什麼N個元素中選出前M個，什麼出現頻率最多的x個等，再就是要求構建堆的時候採用 heapify 的方式(表現在要求複雜度優於O(nlogn)) 等，大多都在此範疇內。
比如 Leetcode 347 就可以用 java.util.PriorityQueue，參考程式碼:
import java.util.TreeMap; import java.util.PriorityQueue; import java.util.LinkedList; //import java.util.List; class Solution { //放入 PriorityQueue 中的元素 private class Freq implements Comparable<Freq> { public int e, freq; //構造器 public Freq(int key, int freq) { this.e = key; this.freq = freq; } //由於 java.util.PriorityQueue 是小頂堆，正常些比較邏輯 @Override public int compareTo(Freq another) { return this.freq - another.freq; } } public List<Integer> topKFrequent(int[] nums, int k) { //首先把數組放入 map 統計頻次 TreeMap<Integer, Integer> map = new TreeMap<>(); for(int num : nums) { if(map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } PriorityQueue<Freq> queue = new PriorityQueue<>(); //不使用比較器 //遍歷 map 放入 PriorityQueue 中 for(int key : map.keySet()) { //前 k - 1 個元素直接放進去 if(queue.size() < k) { queue.add(new Freq(key, map.get(key))); } else if(map.get(key) > queue.peek().freq) { //替換最小的 queue.remove(); queue.add(new Freq(key, map.get(key))); } } //把 queue 中的結果整理出來，放入結果集中 LinkedList<Integer> res = new LinkedList<>(); while(!queue.isEmpty()) { res.addFirst(queue.remove().e); //因為現出來的是頻率相對低的 } return res; } }然後，程式碼優化以下(採用傳入比較器，Lambda表達式代替匿名類捕獲外部map):
- 可以捕獲外部 map，所以邏輯自然簡潔了(但是不容易想到)
不難看出，小頂堆用的還是蠻多的。
擴展
想讓樹的層次變少，那麼久使用
K叉堆吧
但是 K 叉堆(K可以取值3以上的值)需要考慮的孩子多餘兩個，此時 sift up 或者 sift down 需要的比較孩子，交換根與孩子的策略就需要重寫一下。
也就是說，調整的時候需要考慮的邏輯會多一些。
其他堆: 比如索引堆(可以操作除堆頂元素之外的元素)，二項堆，斐波那契堆。
(一般相關語言實現的堆，就是最常用最常見，最有用的堆)
對於堆的認識，我也僅停留在最基本的堆。
不多言了，還是把程式碼倉庫貼一下吧 gayhub。
