圖解堆結(jié)構(gòu)、堆排序及堆的應(yīng)用
前言
這次我們介紹另一種時(shí)間復(fù)雜度為 O(nlogn) 的選擇類(lèi)排序方法叫做堆排序。
我將從以下幾個(gè)方面介紹：
- 堆的結(jié)構(gòu)
- 堆排序
- 優(yōu)化的堆排序
- 原地堆排序
- 堆的應(yīng)用
堆的結(jié)構(gòu)
什么是堆?我給出了百度的定義，如下：
堆(Heap)是計(jì)算機(jī)科學(xué)中一類(lèi)特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱(chēng)。堆通常是一個(gè)可以被看做一棵 完全二叉樹(shù) 的數(shù)組對(duì)象。
堆總是滿足下列性質(zhì)：
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值。
- 堆總是一棵完全二叉樹(shù)。
將根節(jié)點(diǎn)最大的堆叫做最大堆，根節(jié)點(diǎn)最小的堆叫做最小堆。
下圖展示了一個(gè)最大堆的結(jié)構(gòu)：
可見(jiàn)，堆中某個(gè)節(jié)點(diǎn)的值總是小于等于其父節(jié)點(diǎn)的值。
由于堆是一棵完全二叉樹(shù)，因此我們可以對(duì)每一層進(jìn)行編號(hào)，如下：
我們完全可以使用數(shù)組存放這些元素，那如何確定存放的位置呢?利用如下公式：
- 父節(jié)點(diǎn)：parent(i) = (i-1)/2
- 左孩子：leftChild(i) = 2*i+1
- 右孩子：rightChild(i) = 2*i+2
相關(guān)代碼如下：
- private int parent(int index) {
- return (index - 1) / 2;
- }
- private int leftChild(int index) {
- return index * 2 + 1;
- }
- private int rightChild(int index) {
- return index * 2 + 2;
- }
添加元素
向堆中添加元素的步驟如下：
- 將新元素放到數(shù)組的末尾。
- 獲取新元素的父親節(jié)點(diǎn)在數(shù)組中的位置，比較新元素和父親節(jié)點(diǎn)的值，如果父親節(jié)點(diǎn)的值小于新元素的值，那么兩者交換。以此類(lèi)推，不斷向上比較，直到根節(jié)點(diǎn)結(jié)束。
下圖展示了添加元素的過(guò)程：
添加元素的過(guò)程也叫做 siftUp ，代碼如下：
- // Array是自己實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組
- private Array<E> data;
- public void add(E e) {
- data.addLast(e);
- siftUp(data.getSize() - 1);
- }
- private void siftUp(int k) {
- while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
- data.swap(k, parent(k));
- k = parent(k);
- }
- }
刪除元素
刪除元素其實(shí)就是刪除堆頂?shù)脑?，步驟如下：
- 讓數(shù)組最后一個(gè)元素和數(shù)組第一個(gè)元素(堆頂元素)交換。
- 交換完后，刪除數(shù)組最后的元素。
- 讓堆頂元素和左右孩子節(jié)點(diǎn)比較，如果堆頂元素比左右孩子節(jié)點(diǎn)中最大的元素還要大，那么滿足堆的性質(zhì)，直接退出。否則如果堆頂元素比左右孩子節(jié)點(diǎn)中最大的元素小，那么堆頂元素就和最大的元素交換，然后繼續(xù)重復(fù)執(zhí)行以上操作，只不過(guò)這時(shí)候把堆頂元素稱(chēng)為父節(jié)點(diǎn)更好。
下圖展示了刪除元素的過(guò)程：
刪除元素的過(guò)程也叫做 siftDown ，代碼如下：
- // 這里我們不命名為remove，命名為extractMax，抽取堆頂最大元素
- public E extractMax() {
- E ret = findMax();
- // 讓最后一個(gè)葉子節(jié)點(diǎn)補(bǔ)到根節(jié)點(diǎn)，然后讓它下沉
- // (為什么是取最后一個(gè)葉子節(jié)點(diǎn)，因?yàn)榧词谷∽咦詈笠粋€(gè)葉子節(jié)點(diǎn)，依舊能保持是一棵完全二叉樹(shù))
- data.swap(0, data.getSize() - 1);
- data.removeLast();
- siftDown(0);
- return ret;
- }
- private void siftDown(int k) {
- while (leftChild(k) < data.getSize()) {
- int j = leftChild(k);
- if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
- j = rightChild(k);
- // data[j]是leftChild和rightChild中的最大值
- }
- // 如果父節(jié)點(diǎn)比左右孩子中的最大值還要大，那么說(shuō)明沒(méi)有問(wèn)題，直接退出
- if (data.get(k).compareTo(data.get(j)) >= 0) {
- break;
- }
- // 否則交換
- data.swap(k, j);
- k = j;
- }
- }
最大堆的完整代碼
堆排序
通過(guò)上面的介紹，我們應(yīng)該明白了堆的結(jié)構(gòu)，堆的添加和刪除元素操作是如何完成的。那么對(duì)于堆排序來(lái)說(shuō)，就是小菜一碟了，因?yàn)槎雅判蚓褪怯玫搅硕训奶砑雍蛣h除操作，步驟如下：
- 將數(shù)組中元素一個(gè)個(gè)添加到堆(最大堆)中。
- 添加完成后，每次取出一個(gè)元素倒序放入到數(shù)組中。
堆排序代碼：
- ublic static void sort(Comparable[] arr) {
- int n = arr.length;
- // MaxHeap是自己實(shí)現(xiàn)的最大堆
- MaxHeap<Comparable> maxHeap = new MaxHeap<>(n);
- for (int i = 0; i < n; i++) {
- maxHeap.add(arr[i]);
- }
- for (int i = n - 1; i >= 0; i--) {
- arr[i] = maxHeap.extractMax();
- }
- }
堆排序完整代碼
優(yōu)化的堆排序
在上述的堆排序中，我們?cè)趯?shù)組中元素添加到堆時(shí)，都是一個(gè)個(gè)添加，是否有優(yōu)化的方法呢?答案是有的，我們可以將數(shù)組直接轉(zhuǎn)換成堆，這種操作叫做 Heapify 。
Heapify 就是從最后一個(gè)節(jié)點(diǎn)開(kāi)始，判斷父節(jié)點(diǎn)是否比孩子節(jié)點(diǎn)大，不是就 siftDown 。 Heapify 操作的時(shí)間復(fù)雜度是 O(n) ，相比一個(gè)個(gè)添加的時(shí)間復(fù)雜度是 O(nlogn) ，可見(jiàn)性能提升了不少。
假設(shè)我們有數(shù)組： [15, 18, 12, 16, 22, 28, 16, 45, 30, 52] ，下圖展示了對(duì)其進(jìn)行 Heapify 的過(guò)程。
優(yōu)化的堆排序代碼：
- public static void sort(Comparable[] arr) {
- int n = arr.length;
- // MaxHeap是自己實(shí)現(xiàn)的最大堆，當(dāng)傳入數(shù)組作為構(gòu)造參數(shù)時(shí)，會(huì)對(duì)其進(jìn)行heapify
- MaxHeap<Comparable> maxHeap = new MaxHeap<>(arr);
- for (int i = n - 1; i >= 0; i--) {
- arr[i] = maxHeap.extractMax();
- }
- }
- // 構(gòu)造方法
- public MaxHeap(E[] arr) {
- data = new Array<>(arr);
- // 將數(shù)組堆化的過(guò)程就是從最后一個(gè)節(jié)點(diǎn)開(kāi)始，判斷父節(jié)點(diǎn)是否比子節(jié)點(diǎn)大，不是就siftDown
- for (int i = parent(arr.length - 1); i >= 0; i--) {
- siftDown(i);
- }
- }
優(yōu)化的堆排序完整代碼
原地堆排序
原地堆排序可以讓我們的空間復(fù)雜度變?yōu)?O(1) ，因?yàn)椴徽加眯碌臄?shù)組。
原地堆排序類(lèi)似于堆的刪除元素，步驟如下：
- Heapify
- siftDown
- siftDown
下圖展示了原地堆排序的過(guò)程：
原地堆排序代碼：
- public static void sort(Comparable[] arr) {
- int n = arr.length;
- // heapify
- for (int i = parent(n-1); i >= 0; i--) {
- siftDown(arr, n, i);
- }
- // 核心代碼
- for (int i = n - 1; i > 0; i--) {
- swap(arr, 0, i);
- siftDown(arr, i, 0);
- }
- }
- private static void swap(Object[] arr, int i, int j) {
- Object t = arr[i];
- arr[i] = arr[j];
- arr[j] = t;
- }
- private static void siftDown(Comparable[] arr, int n, int k) {
- while (leftChild(k) < n) {
- int j = leftChild(k);
- if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
- j = rightChild(k);
- }
- // 如果父節(jié)點(diǎn)比左右孩子中的最大值還要大，那么說(shuō)明沒(méi)有問(wèn)題，直接退出
- if (arr[k].compareTo(arr[j]) >= 0) {
- break;
- }
- // 否則交換
- swap(arr, k, j);
- k = j;
- }
- }
原地堆排序完整代碼
堆的應(yīng)用
優(yōu)先級(jí)隊(duì)列
一旦我們掌握了堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，那么優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)就很簡(jiǎn)單了，只需要弄清楚優(yōu)先級(jí)隊(duì)列需要有哪些接口就行。JDK 中自帶的 PriorityQueue 就是用堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列，不過(guò)需要注意 PriorityQueue 內(nèi)部使用的是最小堆。
優(yōu)先級(jí)隊(duì)列完整代碼
Top K 問(wèn)題
Top K 問(wèn)題就是求解 前 K 個(gè) 最大的元素或者最小的元素。元素個(gè)數(shù)不確定，數(shù)據(jù)量可能很大，甚至源源不斷到來(lái)，但需要知道目前為止前 K 個(gè)最大或最小的元素。當(dāng)然問(wèn)題還可能變?yōu)榍蠼?第 K 個(gè) 最大的元素或最小的元素。
通常我們有如下解決方案：
- 使用JDK中自帶的排序，如 Arrays.sort() ，由于底層使用的快速排序，所以時(shí)間復(fù)雜度為 O(nlogn) 。但是如果 K 取值很小，比如是 1，即取最大值，那么對(duì)所有元素排序就沒(méi)有必要了。
- 使用簡(jiǎn)單選擇排序，選擇 K 次，那么時(shí)間復(fù)雜度為 O(n*K) ，如果 K 大于 logn，那還不如快排呢!
上述兩種思路都是假定所有元素已知，如果元素個(gè)數(shù)不確定，且數(shù)據(jù)源源不斷到來(lái)的話，就無(wú)能為力了。
下面提供一種新的思路：
我們維護(hù)一個(gè)長(zhǎng)度為 K 的數(shù)組，最前面 K 個(gè)元素就是目前最大的 K 個(gè)元素，以后每來(lái)一個(gè)新元素，都先找數(shù)組中的最小值，將新元素與最小值相比，如果小于最小值，則什么都不變，如果大于最小值，則將最小值替換為新元素。這樣一來(lái)，數(shù)組中維護(hù)的永遠(yuǎn)是最大的 K 個(gè)元素，不管數(shù)據(jù)源有多少，需要的內(nèi)存開(kāi)銷(xiāo)都是固定的，就是長(zhǎng)度為 K 的數(shù)組。不過(guò)，每來(lái)一個(gè)元素，都需要找到最小值，進(jìn)行 K 次比較，是否有辦法能減少比較次數(shù)呢?
當(dāng)然，這時(shí)候堆就要登場(chǎng)了，我們使用最小堆維護(hù)這 K 個(gè)元素，每次來(lái)新的元素，只需要和根節(jié)點(diǎn)比較，小于等于根節(jié)點(diǎn)，不需要變化，否則用新元素替換根節(jié)點(diǎn)，然后 siftDown 調(diào)整堆即可。此時(shí)的時(shí)間復(fù)雜度為 O(nlogK) ，相比上述兩種方法，效率大大提升，且空間復(fù)雜度也大大降低。
Top K 問(wèn)題代碼：
- public class TopK<E extends Comparable<E>> {
- private PriorityQueue<E> p;
- private int k;
- public TopK(int k) {
- this.k = k;
- this.p = new PriorityQueue<>(k);
- }
- public void addAll(Collection<? extends E> c) {
- for (E e : c) {
- add(e);
- }
- }
- public void add(E e) {
- // 未滿k個(gè)時(shí)，直接添加
- if (p.size() < k) {
- p.add(e);
- return;
- }
- E head = p.peek();
- if (head != null && head.compareTo(e) >= 0) {
- // 小于等于TopK中的最小值，不用變
- return;
- }
- // 否則，新元素替換原來(lái)的最小值
- p.poll();
- p.add(e);
- }
- /**
- * 獲取當(dāng)前的最大的K個(gè)元素
- *
- * @param a 返回類(lèi)型的空數(shù)組
- * @param <T>
- * @return TopK以數(shù)組形式
- */
- public E[] toArray(E[] a) {
- return p.toArray(a);
- }
- /**
- * 獲取第K個(gè)最大的元素
- *
- * @return 第K個(gè)最大的元素
- */
- public E getKth() {
- return p.peek();
- }
- public static void main(String[] args) {
- TopK<Integer> top5 = new TopK<>(5);
- top5.addAll(Arrays.asList(88, 1, 5, 7, 28, 12, 3, 22, 20, 70));
- System.out.println("top5：" + Arrays.toString(top5.toArray(new Integer[0])));
- System.out.println("5th：" + top5.getKth());
- }
- }
這里我們直接利用 JDK 自帶的由最小堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列 PriorityQueue 。
依此思路，可以實(shí)現(xiàn)求前 K 個(gè)最小元素，只需要在實(shí)例化 PriorityQueue 時(shí)傳入一個(gè)反向比較器參數(shù)，然后更改 add 方法的邏輯。
中位數(shù)
堆也可以用于求解中位數(shù)，數(shù)據(jù)量可能很大且源源不斷到來(lái)。
注意：如果元素個(gè)數(shù)是偶數(shù)，那么我們假定中位數(shù)取任意一個(gè)都可以。
有了上面的例子，這里就很好理解了。我們使用兩個(gè)堆，一個(gè)最大堆，一個(gè)最小堆，步驟如下：
- 添加的第一個(gè)元素作為中位數(shù) m，最大堆維護(hù) <= m 的元素，最小堆維護(hù) >= m 的元素，兩個(gè)堆都不包含 m。
- 當(dāng)添加第二個(gè)元素 e 時(shí)，將 e 與 m 比較，若 e <= m，則將其加入到最大堆中，否則加入到最小堆中。
- 如果出現(xiàn)最小堆和最大堆的元素個(gè)數(shù)相差 >= 2，則將 m 加入元素個(gè)數(shù)少的堆中，然后讓元素個(gè)數(shù)多的堆將根節(jié)點(diǎn)移除并賦值給 m。
- 以此類(lèi)推不斷更新。
假設(shè)有數(shù)組 [20, 30, 40, 50, 2, 4, 3, 5, 7, 8, 10] 。
下圖展示了整個(gè)操作的過(guò)程：
求解中位數(shù)的代碼：
- public class Median<E extends Comparable<E>> {
- /**
- * 最小堆
- */
- private PriorityQueue<E> minP;
- /**
- * 最大堆
- */
- private PriorityQueue<E> maxP;
- /**
- * 當(dāng)前中位數(shù)
- */
- private E m;
- public Median() {
- this.minP = new PriorityQueue<>();
- this.maxP = new PriorityQueue<>(11, Collections.reverseOrder());
- }
- private int compare(E e, E m) {
- return e.compareTo(m);
- }
- public void addAll(Collection<? extends E> c) {
- for (E e : c) {
- add(e);
- }
- }
- public void add(E e) {
- // 第一個(gè)元素
- if (m == null) {
- m = e;
- return;
- }
- if (compare(e, m) <= 0) {
- // 小于等于中值，加入最大堆
- maxP.add(e);
- } else {
- // 大于中值，加入最大堆
- minP.add(e);
- }
- if (minP.size() - maxP.size() >= 2) {
- // 最小堆元素個(gè)數(shù)多，即大于中值的數(shù)多
- // 將 m 加入到最大堆中，然后將最小堆中的根移除賦給 m
- maxP.add(m);
- m = minP.poll();
- } else if (maxP.size() - minP.size() >= 2) {
- minP.add(m);
- m = maxP.poll();
- }
- }
- public E getMedian() {
- return m;
- }
- public static void main(String[] args) {
- Median<Integer> median = new Median<>();
- median.addAll(Arrays.asList(20, 30, 40, 50, 2, 4, 3, 5, 7, 8, 10));
- System.out.println(median.getMedian());
- }
- }
