一、完全二叉樹

堆是一種完全二叉樹，什么是完全二叉樹？

簡(jiǎn)單的說(shuō)，一棵滿二叉樹表示的是所有節(jié)點(diǎn)全部飽和，最后一層全部占滿：

而完全二叉樹指的是滿二叉樹的最后一層，所有葉子節(jié)點(diǎn)都從左往順序排滿：

完全二叉樹的特點(diǎn)非常簡(jiǎn)單，除了最后一層，其他各層節(jié)點(diǎn)都是滿的，而最后一層，所有節(jié)點(diǎn)從左往右依次排滿。它并不關(guān)心節(jié)點(diǎn)元素的大小，只與這一結(jié)構(gòu)特點(diǎn)有關(guān)。

二、堆結(jié)構(gòu)

前面說(shuō)到，堆是一種特殊的完全二叉樹，除了符合完全二叉樹的結(jié)構(gòu)特點(diǎn)，它還有另一個(gè)特性，由這個(gè)特性，我們又可以將堆分為——大根堆、小根堆。

大根堆：每個(gè)節(jié)點(diǎn)比它的子節(jié)都要大。

小根堆：和大根堆相反，每個(gè)節(jié)點(diǎn)比它的子節(jié)點(diǎn)都要小。

注意，堆只關(guān)心父節(jié)點(diǎn)與子節(jié)點(diǎn)之間的大小，要么父節(jié)點(diǎn)比子節(jié)點(diǎn)都大，視為大根堆；要么父節(jié)點(diǎn)比子節(jié)點(diǎn)都小，視為小根堆。只要保證這一點(diǎn)，再加上完全二叉樹的特點(diǎn)，就是一個(gè)堆結(jié)構(gòu)。至于全部節(jié)點(diǎn)是否呈現(xiàn)一種左大右小或左小右大的關(guān)系，堆并不關(guān)心。

如何實(shí)現(xiàn)一個(gè)堆？

堆并不是一個(gè)實(shí)際存在的物理結(jié)構(gòu)，它需要通過(guò)一個(gè)一維數(shù)組來(lái)表示。實(shí)際上，數(shù)組表示了堆的一種對(duì)應(yīng)關(guān)系。

有了這樣一種對(duì)應(yīng)關(guān)系，我們可以得到下面 3 個(gè)公式：

已知任意位置 index，求其父節(jié)點(diǎn)和子節(jié)點(diǎn)位置：

父節(jié)點(diǎn)：int fatherIdx = (index - 1) / 2; // 注意， (0 - 1) / 2 = 0，實(shí)際上double->int 是向0取整，或絕對(duì)值向下取整。

左子節(jié)點(diǎn)：int leftIdx = index * 2 + 1;

右子節(jié)點(diǎn)：int rightIdx = index * 2 + 2;

例如，4 位置的父節(jié)點(diǎn)是 1 位置，(4 - 1) / 2 = 1 ，向下取整。

有了位置關(guān)系，剩下的工作就是實(shí)現(xiàn)大根堆或小根堆，一般情況，大根堆可以快速返回整個(gè)堆中的最大值，比較常用，以下就以大根堆為例。

接下來(lái)，我們通過(guò)代碼來(lái)詳細(xì)解析如何實(shí)現(xiàn)一個(gè)堆結(jié)構(gòu)。

三、堆結(jié)構(gòu)的實(shí)現(xiàn)

以數(shù)組為基礎(chǔ)，構(gòu)建一個(gè)大根堆的對(duì)應(yīng)關(guān)系。這個(gè)堆結(jié)構(gòu)需要實(shí)現(xiàn)以下幾個(gè)公共方法：

push 入堆

pop 出堆

isEmpty 是否為空

isFull 是否已滿

實(shí)現(xiàn)堆結(jié)構(gòu)的過(guò)程要始終緊扣兩個(gè)特點(diǎn)：

完全二叉樹的特點(diǎn)

大根堆的特點(diǎn)

只有這兩點(diǎn)滿足，它才是一個(gè)正確的堆。

當(dāng)push一個(gè)元素的時(shí)候，由于實(shí)現(xiàn)結(jié)構(gòu)是數(shù)組，因此始終是追加到數(shù)組的末尾，但我們可以通過(guò)特定的方法來(lái)實(shí)現(xiàn)“堆結(jié)構(gòu)”的調(diào)整。

想象這個(gè)元素被追加到了堆結(jié)構(gòu)最后一層的末尾，首先完全二叉樹的條件就滿足了。

但是大根堆的特點(diǎn)呢？這時(shí)就需要從末尾開始，向上與父節(jié)點(diǎn)比大小，大的站在父節(jié)點(diǎn)的位置，然后重復(fù)這個(gè)過(guò)程，直到這個(gè)元素不再比父節(jié)點(diǎn)大，或已經(jīng)站在了 0 的位置。

public void push(int value) {if (isFull())throw new RuntimeException("heap is full");heap[heapSize] = value;heapInsert(heap, heapSize++);}private void heapInsert(int[] arr, int index) {// 當(dāng)前位置元素比父節(jié)點(diǎn)大，交換位置，重置當(dāng)前位置// 循環(huán)條件有兩點(diǎn)作用：1、當(dāng)前節(jié)點(diǎn)>父節(jié)點(diǎn)（明顯）// 2、由于 (0-1)/2=0，如果index已經(jīng)是0位置，出現(xiàn)相等的情況，跳出循環(huán)（隱藏）while (arr[index] > arr[(index - 1) / 2]) {SortUtil.swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}

而如果 pop 一個(gè)元素，稍微復(fù)雜一些，首先，我們需要記錄下 0 位置上的元素，然后用堆的最后一個(gè)元素補(bǔ)位，heapSize 縮減 1 位，這幾步操作是為了保證取出元素后依然是一個(gè)完全二叉樹。

然后我們需要從 0 位置上（已經(jīng)替換為最后一個(gè)位置上的數(shù)）與子節(jié)點(diǎn)比較，找到最大的子節(jié)點(diǎn)，然后與其交換（下沉），循環(huán)直到下沉到“堆的最后一層”或子節(jié)點(diǎn)都比自己小（終止條件）：

public int pop() {int max = heap[0];// 1、要拿掉根節(jié)點(diǎn)，因?yàn)橐ＷC是一個(gè)完全二叉樹，所以第一步，我們?nèi)∽詈笠粋€(gè)元素補(bǔ)位SortUtil.swap(heap, 0, heapSize - 1);// 2、heapSize縮減一位heapSize--;// 2、再執(zhí)行heapify下沉操作，因?yàn)檠a(bǔ)位的元素可能不滿足大根的特點(diǎn)，所以要向下比較heapify(heap, 0, heapSize);return max;}private void heapify(int[] arr, int i, int heapSize) {int left = 2 * i + 1;// 若左孩子沒(méi)有越界，證明存在下一級(jí)，有可能需要下沉while (left < heapSize) {// 選出子節(jié)點(diǎn)中最大的那個(gè)位置int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;largest = arr[largest] > arr[i] ? largest : i;if (largest == i)break;else {// 執(zhí)行交換SortUtil.swap(arr, largest, i);i = largest;left = 2 * i + 1;}}}

以下是完整代碼：

/*** 大根堆** @data 2021/5/15 16:46*/ public class Code2_MaxHeap {/*** 堆容器*/private int[] heap;/*** 元素限制*/private final int limit;/*** 堆大小*/private int heapSize;public Code2_MaxHeap(int limit) {this.heap = new int[limit];this.limit = limit;this.heapSize = 0;}public void push(int value) {if (isFull())throw new RuntimeException("heap is full");heap[heapSize] = value;heapInsert(heap, heapSize++);}/*** 1、因?yàn)槭菙?shù)組表示的堆結(jié)構(gòu)，每次插入都是在末尾，因此，index每次都是堆的最后一個(gè)值* 2、利用堆結(jié)構(gòu)的特點(diǎn)，可以快速求出當(dāng)前位置的父節(jié)點(diǎn)在數(shù)組中的下標(biāo)，即(index - 1)/2* 3、比較當(dāng)前位置與父節(jié)點(diǎn) 大小，如果比父大，交換，然后當(dāng)前位置變?yōu)楦腹?jié)點(diǎn)位置* 4、重復(fù) 2、3，繼續(xù)向上比較，要么直到?jīng)]有父節(jié)點(diǎn)，那么while的條件會(huì)在兩數(shù)相等時(shí)退出，要么不比父節(jié)點(diǎn)大，也停止向上比較。*/private void heapInsert(int[] arr, int index) {// 當(dāng)前位置元素比父節(jié)點(diǎn)大，交換位置，重置當(dāng)前位置while (arr[index] > arr[(index - 1) / 2]) {SortUtil.swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public int pop() {int max = heap[0];// 1、要拿掉根節(jié)點(diǎn)，因?yàn)橐ＷC是一個(gè)完全二叉樹，所以第一步，我們?nèi)∽詈笠粋€(gè)元素補(bǔ)位SortUtil.swap(heap, 0, heapSize - 1);// 2、heapSize縮減一位heapSize--;// 2、再執(zhí)行heapify下沉操作，因?yàn)檠a(bǔ)位的元素可能不滿足大根的特點(diǎn)，所以要向下比較heapify(heap, 0, heapSize);return max;}private void heapify(int[] arr, int i, int heapSize) {int left = 2 * i + 1;// 若左孩子沒(méi)有越界，證明存在下一級(jí)，有可能需要下沉while (left < heapSize) {// 選出子節(jié)點(diǎn)中最大的那個(gè)位置int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;largest = arr[largest] > arr[i] ? largest : i;if (largest == i)break;else {// 執(zhí)行交換SortUtil.swap(arr, largest, i);i = largest;left = 2 * i + 1;}}}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == heap.length;}}

測(cè)試代碼：

public static void main(String[] args) {int value = 1000;int limit = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {int curLimit = (int) (Math.random() * limit) + 1;Code2_MaxHeap my = new Code2_MaxHeap(curLimit);RightMaxHeap test = new RightMaxHeap(curLimit);int curOpTimes = (int) (Math.random() * limit);for (int j = 0; j < curOpTimes; j++) {if (my.isEmpty() != test.isEmpty()) {System.out.println("Oops!");}if (my.isFull() != test.isFull()) {System.out.println("Oops!");}if (my.isEmpty()) {int curValue = (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else if (my.isFull()) {if (my.pop() != test.pop()) {System.out.println("Oops!");}} else {if (Math.random() < 0.5) {int curValue = (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else {if (my.pop() != test.pop()) {System.out.println("Oops!");}}}}}System.out.println("finish!");}/*** 遍歷數(shù)組選出一個(gè)最大值 pop* 用于驗(yàn)證與自定義MaxHeap.pop的值是相等的。*/ class RightMaxHeap {private int[] arr;private final int limit;private int size;public RightMaxHeap(int limit) {arr = new int[limit];this.limit = limit;size = 0;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == limit;}public void push(int value) {if (size == limit) {throw new RuntimeException("heap is full");}arr[size++] = value;}public int pop() {int maxIndex = 0;for (int i = 1; i < size; i++) {if (arr[i] > arr[maxIndex]) {maxIndex = i;}}int ans = arr[maxIndex];arr[maxIndex] = arr[--size];return ans;} }

如果一個(gè)堆的某個(gè)位置的數(shù)變了，還不知道變大還是變小，如何重新調(diào)整堆結(jié)構(gòu)？ 這個(gè)位置 i 順序調(diào)用一下 heapinsert 和 heapify 整個(gè)堆就會(huì)自動(dòng)整理好。

四、優(yōu)先級(jí)隊(duì)列與堆

java.util.PriorityQueue<T>? 是一個(gè)優(yōu)先級(jí)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，它的底層實(shí)現(xiàn)就是用堆來(lái)完成的。另外，它是允許添加重復(fù)元素的，這與 TreeMap 不允許添加重復(fù)元素有區(qū)別。

這種結(jié)構(gòu)可以立刻返回最大值或最小值，指定一個(gè)比較器（參考《比較器的使用》），符合“正減升，反減降”的口訣。如果是按升序設(shè)定比較器，那么 peek 或 poll 方法就會(huì)返回最小值。反之就是最大值。

public static void main(String[] args) {// 小根堆PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o1 - o2);heap.add(5);heap.add(5);heap.add(5);heap.add(3);// 5 , 3System.out.println(heap.peek());heap.add(7);heap.add(0);heap.add(7);heap.add(0);heap.add(7);heap.add(0);System.out.println(heap.peek());while (!heap.isEmpty()) {System.out.println(heap.poll());}}

五、堆的時(shí)間復(fù)雜度

堆結(jié)構(gòu)的時(shí)間復(fù)雜度主要是看 heapInsert 和 heapify 兩個(gè)方法。

它們的操作始終與樹的高度緊密相關(guān)，每次只有一個(gè)節(jié)點(diǎn)調(diào)換，整體是復(fù)雜度都是 O(logN)。

總結(jié)

以上是生活随笔為你收集整理的经典数据结构——堆的实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。