1. 為什么要引入堆？
1.1 堆的應用場景
有時候我們面臨一種實際應用場景需要根據任務的重要程度而劃分優先級，對優先級高的任務提供優先服務，
優先級佇列(Priority Queue)：取出元素的順序是依據優先級大小，而不是元素進入佇列的先后順序，
優先級佇列實作要求：維護這樣一種結構，取出資料時總是取出集合中的最值(可以是最大值，也可以是最小值)
1.2 堆的引入
?? 什么樣的結構可以高效地存盤和維護集合使其滿足優先級佇列的特點呢？
??陣列：不排序
- 插入——元素總是插入尾部(維護一個size欄位) ——
O(1) - 洗掉——查找最值——
O(n)，從陣列中刪去需要移動元素——O(n)
??鏈表：不排序
- 插入——元素總是插入頭部或者尾部 ——
O(1) - 洗掉——查找最值——
O(n)，從陣列中刪去最值結點——O(1)
??有序陣列
- 插入——找到合適位置 ——
O(n)或者二分法O(logn)；移動元素并插入O(n) - 洗掉——刪去最后一個元素——
O(1)
??有序鏈表
- 插入——找到合適位置 ——
O(n)；插入O(1) - 洗掉——刪去首元素或者最后一個元素——
O(1)
結果發現，總有一個操作的時間復雜度讓人不滿意??
?? 是否可以采用二叉樹存盤結構？
二叉搜索樹的查找和插入，較好的時間復雜度都是O(logn)的，是樹的高度，但是如果洗掉不當，會導致樹退化成線性表，
如果采用樹結構，更應該關注洗掉，最好是將樹根作為最值存盤點，父結點的值比子結點的值大，采用完全二叉樹的結構最好，
堆
??結構性：用陣串列示的完全二叉樹
??有序性：任一結點的關鍵字是其子樹所有結點的最大值(或最小值)
MaxHeap大頂堆
MinHeap小頂堆
用陣串列示堆：圖中圓內值為下標
求父節點下標需要向下取整
??注意：0的父節點 (0-1)/2 = 0
2. 堆的描述
型別名稱：最大堆(MaxHeap)
資料物件集: 完全二叉樹，每個結點的元素值都不小于其子結點的元素值
操作集:
public MaxHeap(int maxSize): 創建一個空的最大堆
public boolean isFull(): 判斷最大堆是否已滿
public boolean isEmpty(): 判斷最大堆是否為空
public int peek(): 查看堆頂元素值
public void push(int value): 將元素插入最大堆
public int pop(): 回傳最大堆中的最大元素
private void heapInsert(int[] arr, int index): 實際插入元素的封裝操作
private void heapify(int[] arr, int index, int heapSize): 洗掉元素后維護堆特性的封裝
private void swap(int[] arr, int i, int j): 交換元素的封裝
public List<Integer> getAllElements(): 獲取堆全部有效元素
3. 圖解原理
整個堆結構中，最復雜的兩個操作一個是插入元素保持堆特性，一個是洗掉最大元素保持堆特性，本節主要從這兩方面的重點??函式進行舉例講解，
3.1 heapInsert
插入元素之后要保持堆的特性(本例取大根堆特性)
我們用heapSize標識待插入元素的位置，每次插入元素就知道其下標，因為只有父結點值大，所以新插入元素不停地與父節點PK大小，如果新插入元素更大，那就與父結點交換，之后繼續PK，直到無法PK勝出或者已經到達堆頂0位置為止，
private void heapInsert(int[] arr, int index) {
// 注意假如最后能比到0，此時下一次比較會跟自己比，必不可能大，所以會退出
while (arr[index] > arr[(index - 1) / 2]) { // index 比 父 大
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
3.2 heapify
假設堆不為空，取出堆頂元素，并將其從堆中刪掉，
若此時堆為下圖所示，圓中為實際結點值，右側為陣列記憶體存盤值:
將8保存給變數ans,然后交換8和6(最后一個結點)，然后heapSize--，將8邏輯洗掉，最后對堆頂元素6進行heapify，使heapify后的陣列保持堆特性，
// 回傳最大值
public int pop() {
int ans = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return ans;
}
堆頂的6與自己的左右孩子PK(因為左孩子下標為1小于heapSize=4，所以是合法的，且右孩子也合法)，與較大孩子且能PK贏6的進行交換，即6與7進行交換，
隨后重復上述程序，發現6無需移動，此時完成heapify
// heapSize管著不會越界找孩子，左孩子若越界則右孩子必越界
private void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while ( left < heapSize) { // 如果有左孩子
int right = left + 1;
// 如果有右孩子,且右孩子值比左孩子值大
// 選出較大孩子
int largest = (right < heapSize && arr[right] > arr[left]) ? right : left;
// 孩子和index對應的值PK，誰大誰給largest
largest = arr[largest] > arr[index] ? largest : index;
// 不必下沉
if (largest == index) {
break;
}
// index 和 較大孩子 largest要互換
swap(arr, largest, index);
index = largest;
left = index * 2 + 1; // 繼續考察左孩子
}
}
4. 完整代碼
AlgoUtils代碼參考之前的文章
package com.ravi.datastructure.heap;
import com.ravi.algorithm.util.AlgoUtils;
import java.util.ArrayList;
import java.util.List;
/**
* @author ravilian
* max Heap
*/
public class MaxHeap {
private int[] heap;
private final int maxSize;
private int heapSize;
public MaxHeap(int maxSize) {
heap = new int[maxSize];
this.maxSize = maxSize;
heapSize = 0;
}
public boolean isEmpty() {
// 邏輯大小
return heapSize == 0;
}
public boolean isFull() {
return heapSize == maxSize;
}
public int peek() {
if (heapSize == 0) {
throw new RuntimeException("堆為空!");
}
return heap[0];
}
public void push(int value) {
if (heapSize == maxSize) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
heapInsert(heap, heapSize++);
}
// 回傳最大值
public int pop() {
int ans = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return ans;
}
/**
* 新加進來的數，停在index位置，依次往上移動
* 移動到0位置，或者PK不過父，停
* @param arr
* @param index
*/
private void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) { // index 比 父 大
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/**
* 從index位置往下看，不斷下沉
* 停：較大的孩子不再比index位置的數大; 沒有孩子
* @param arr
* @param index
* @param heapSize
*/
private void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while ( left < heapSize) { // 如果有左孩子
int right = left + 1;
// 如果有右孩子,且右孩子值比左孩子值大
// 選出較大孩子
int largest = (right < heapSize && arr[right] > arr[left]) ? right : left;
// 孩子和index對應的值PK，誰大誰給largest
largest = arr[largest] > arr[index] ? largest : index;
// 不必下沉
if (largest == index) {
break;
}
// index 和 較大孩子 largest要互換
swap(arr, largest, index);
index = largest;
left = index * 2 + 1; // 繼續考察左孩子
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public List<Integer> getAllElements() {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < heapSize; i++) {
ans.add(heap[i]);
}
return ans;
}
public static void main(String[] args) {
int[] detector = AlgoUtils.LogarithmicDetector(10, 200);
AlgoUtils.printArray(detector);
MaxHeap maxHeap = new MaxHeap(20);
for (int i = 0; i < detector.length; i++) {
maxHeap.push(detector[i]);
}
List<Integer> elements = maxHeap.getAllElements();
System.out.println(elements);
}
}
/*
[ 72, 12, 193, 197, 44, 5, 96, 156 ]
[197, 193, 96, 156, 44, 5, 72, 12]
197
/ \
193 96
/ \ / \
156 44 5 72
/
12
*/
5.參考
- 浙大資料結構
- 左程云演算法體系班
- 掘金
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/463493.html
標籤：其他