基於"堆"的底層實現和應用
摘要：
Precious time, which cannot be recovered once lost.
堆是一種特殊的樹（完全二叉樹）。本地主要分享了堆的實現原理，基於堆的排序以及堆的幾個應用。所有原始碼均已上傳至github： 連結
準備
堆的定義：
必須是一個完...
Precious time, which cannot be recovered once lost.
堆是一種特殊的樹（完全二叉樹）。本地主要分享了堆的實現原理，基於堆的排序以及堆的幾個應用。所有原始碼均已上傳至github： 連結
準備
堆的定義：
- 必須是一個完全二叉樹
- 堆中每一個節點的值都必須大於等於（或小於等於）其子樹中每個節點的值。
大頂堆：
對於每個節點的值都大於等於子樹中每個節點值的堆。
小頂堆：
對於每個節點的值都小於等於子樹中每個節點值的堆。
ps：堆化是堆的核心思想,想徹底瞭解堆排序，只需要學會堆化即可。
實現一個大頂堆（小頂堆的實現在github上）
初始化
從下標1開始儲存資料 a[0]相當於一個哨兵
private MinHeap(int capacity) {
arrays = new int[++capacity];
size = capacity;
count = 0;
}複製程式碼
插入
這裡涉及到一個堆化的問題。while迴圈不斷得比較插入的資料和之前堆中的資料大小。滿足條件則進行交換。
private void insert(int data) {
if (count >= size) return;
arrays[++count] = data;
int i = count;
while (i / 2 > 0 && arrays[i] < arrays[i / 2]) {
swap(arrays, i, i / 2);
i = i / 2;
}
}複製程式碼
刪除
為什麼堆也叫優先順序佇列呢，也正因為它也是有線性操作的，刪除只能刪除堆頂元素。
這是 arrays[1] = arrays[count];是刪除堆頂元素前，先取最後一個元素塞入堆頂，然後進行堆化，防止出現 陣列空洞 。
private void removeMin() {
if (count == 0) return;
arrays[1] = arrays[count];
--count;
heapify(arrays, count, 1);
}複製程式碼
堆化有兩種：自下向上堆化和自上向下堆化。這裡以自上向下堆化為例。
private void heapify(int[] arrays, int count, int i) {
while (true) {
int max = i;
if (i * 2 < count && arrays[i] > arrays[i * 2]) max = i * 2;
if (i * 2 + 1 <= count && arrays[max] > arrays[i * 2 + 1]) max = i * 2 + 1;
if (max == i) break;
swap(arrays, i, max);
i = max;
}
}複製程式碼
交換滿足條件的元素
private void swap(int[] arrays, int p, int q) {
int temp = arrays[p];
arrays[p] = arrays[q];
arrays[q] = temp;
}複製程式碼
測試程式碼
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(10);
for (int i = 10; i > 0; --i) {
minHeap.insert(i);
}
System.out.println("小頂堆:");
minHeap.printAll();
System.out.println("刪除堆頂元素後:");
minHeap.removeMin();
minHeap.printAll();
}複製程式碼
測試結果
堆排序
建堆
先將一個無序陣列自上向下堆化，從前往上處理資料變成一個堆。
時間複雜度O(n)
private void buildHeap(int[] arrays, int size) {
for (int i = size / 2; i > 0; --i) {
heapify(arrays, size, i);
}
}複製程式碼
排序
類似於刪除堆頂元素，然後再將這個堆（size-1）再堆化，利兩兩比較，不停的交換元素，以此類推。
時間複雜度O(nlogn)
private void sort() {
buildHeap(arrays, count);
System.out.println("建堆後:");
printAll();
int i = count;
while (i > 1) {
swap(arrays, 1, i--);
heapify(arrays, i, 1);
}
}複製程式碼
測試程式碼
maxHeap.sort();
System.out.println("排序後:");
maxHeap.printAll();複製程式碼
測試結果
求一組動態資料集合的最大 Top K
思考
針對靜態資料，如何在一個包含 n 個數據的陣列中，查詢前 K 大資料呢？可以維護一個大小為 K 的小頂堆，順序遍歷陣列，從陣列中取出取資料與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，並且將這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續遍歷陣列。這樣等陣列中的資料都遍歷完之後，堆中的資料就是前 K 大資料了。
topK
這裡為了更簡便一些，用到了java PriorityQueue （優先佇列的完全體）
- 首先宣告一個大小為k的優先佇列PriorityQueue，然後迴圈arrays陣列，先新增k個數(理解這k個數已經滿足要求了)
- 其次在[k+1,arrays.length]這個範圍內，開始逐個與小頂堆的堆頂進行比較，滿足條件則交換
- 最後將PriorityQueue的資料以此取出即可
offer 新增一個元素並返回true 如果佇列已滿，則返回false
poll 移除並返問佇列頭部的元素 如果佇列為空，則返回null
peek 返回佇列頭部的元素 如果佇列為空，則返回null
private int[] topK(int[] arrays,int k){
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
for (int i = 0; i < arrays.length; i++) {
if (priorityQueue.size() < k){
priorityQueue.offer(arrays[i]);
}else{
int value = priorityQueue.peek();
if (arrays[i] > value){
priorityQueue.poll();
priorityQueue.offer(arrays[i]);
}
}
}
int[] result = new int[k];
int index = 0;
while (!priorityQueue.isEmpty()){
result[index++] = priorityQueue.poll();
}
return result;
}複製程式碼
測試程式碼
public static void main(String[] args) {
GetTopKArrays getTopKArrays = new GetTopKArrays();
int[] arrays = new int[10];
for (int i = 0; i <10 ; i++) {
arrays[i] = i;
}
System.out.println("一組動態資料:");
getTopKArrays.print(arrays);
int k = 3;
int[] result = getTopKArrays.topK(arrays,k);
System.out.println("前三的資料為:");
getTopKArrays.print(result);
}
}複製程式碼
測試結果
求一組動態資料集合的中位數
維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中儲存前半部分資料，小頂堆中儲存後半部分資料，且小頂堆中的資料都大於大頂堆中的資料。
初始化
public Median(int capacity) {
maxHeap = new MaxHeap(capacity);
minHeap = new MinHeap(capacity);
count = 0;
}複製程式碼
插入
- 堆空，插入大頂堆
- data比大頂堆元素大插入小頂堆，否則插入大頂堆
- 如果大頂堆（小頂堆）的資料數量超過了中間值，則需要平衡，移動資料數量多的堆。
private void insert(int data) {
++count;
if (maxHeap.count == 0 && minHeap.count == 0) {
maxHeap.insert(data);
return;
}
int max = maxHeap.removeMax();
if (data > max) {
maxHeap.insert(max);
maxHeap.insert(data);
} else {
maxHeap.insert(max);
minHeap.insert(data);
}
int mid = count / 2;
if (maxHeap.count > mid) {
moveMaxMin(maxHeap, minHeap, maxHeap.count - mid);
}
if (minHeap.count > mid) {
moveMinMax(maxHeap, minHeap, minHeap.count - mid);
}
}複製程式碼
移動
因為這裡是基於上面的堆的實現，沒有封裝徹底，因此手動實現
private void moveMaxMin(MaxHeap maxHeap, MinHeap minHeap, int index) {
for (int i = 0; i < index; i++) {
int data = maxHeap.removeMax();
minHeap.insert(data);
}
}
private void moveMinMax(MaxHeap maxHeap, MinHeap minHeap, int index) {
for (int i = 0; i < index; i++) {
int data = minHeap.removeMin();
maxHeap.insert(data);
}
}複製程式碼
測試程式碼
public static void main(String[] args) {
int capacity = 10;
Median median = new Median(5);
for (int i = 1; i < capacity; i++) {
median.insert(i);
}
System.out.println("大頂堆:");
median.maxHeap.printAll();
System.out.println("小頂堆:");
median.minHeap.printAll();
int midNum = median.maxHeap.removeMax();
System.out.println("中位數為:" + midNum);
}複製程式碼
測試結果
end
您的點贊和關注是對我最大的支援，謝謝！