堆和堆的應用：堆排序和優先佇列

（點選上方公眾號，可快速關註）

來源： Spground 

spground.github.io/2017/07/07/堆和堆的應用：堆排序和優先佇列/

1.堆

堆(Heap))是一種重要的資料結構，是實現優先佇列(Priority Queues)首選的資料結構。由於堆有很多種變體，包括二項式堆、斐波那契堆等，但是這裡只考慮最常見的就是二叉堆（以下簡稱堆）。

堆是一棵滿足一定性質的二叉樹，具體的講堆具有如下性質：父節點的鍵值總是不大於它的孩子節點的鍵值（小頂堆）, 堆可以分為小頂堆和大頂堆，這裡以小頂堆為例，其主要包含的操作有：

• insert()

• extractMin

• peek(findMin)

• delete(i)

由於堆是一棵形態規則的二叉樹，因此堆的父節點和孩子節點存在如下關係：

設父節點的編號為 i, 則其左孩子節點的編號為2*i+1, 右孩子節點的編號為2*i+2
設孩子節點的編號為i, 則其父節點的編號為(i-1)/2

由於二叉樹良好的形態已經包含了父節點和孩子節點的關係資訊，因此就可以不使用連結串列而簡單的使用陣列來儲存堆。

要實現堆的基本操作，涉及到的兩個關鍵的函式

• siftUp(i, x) ： 將位置i的元素x向上調整，以滿足堆得性質，常常是用於insert後，用於調整堆；

• siftDown(i, x)：同理，常常是用於delete(i)後，用於調整堆；

具體的操作如下：

private void siftUp(int i) {

int key = nums[i];

for (; i > 0😉 {

int p = (i – 1) >>> 1;

if (nums[p] <= key)

break;

nums[i] = nums[p];

i = p;

}

nums[i] = key;

}

private void siftDown(int i) {

int key = nums[i];

for (;i < nums.length / 2😉 {

int child = (i << 1) + 1;

if (child + 1 < nums.length && nums[child] > nums[child+1])

child++;

if (key <= nums[child])

break;

nums[i] = nums[child];

i = child;

}

nums[i] = key;

  }

可以看到siftUp和siftDown不停的在父節點和子節點之間比較、交換；在不超過logn的時間複雜度就可以完成一次操作。

有了這兩個基本的函式，就可以實現上述提及的堆的基本操作。

首先是如何建堆，實現建堆操作有兩個思路:

• 一個是不斷地insert（insert後呼叫的是siftUp）

• 另一個將原始陣列當成一個需要調整的堆，然後自底向上地
  在每個位置i呼叫siftDown(i)，完成後我們就可以得到一個滿足堆性質的堆。這裡考慮後一種思路：

通常堆的insert操作是將元素插入到堆尾，由於新元素的插入可能違反堆的性質，因此需要呼叫siftUp操作自底向上調整堆；堆移除堆頂元素操作是將堆頂元素刪除，然後將堆最後一個元素放置在堆頂，接著執行siftDown操作，同理替換堆頂元素也是相同的操作。

建堆

// 建立小頂堆

private void buildMinHeap(int[] nums) {

int size = nums.length;

for (int j = size / 2 – 1; j >= 0; j—)

siftDown(nums, j, size);

}

那麼建堆操作的時間複雜度是多少呢？答案是O(n)。雖然siftDown的操作時間是logn，但是由於高度在遞減的同時，每一層的節點數量也在成倍減少，最後透過數列錯位相減可以得到時間複雜度是O(n)。

extractMin
由於堆的固有性質，堆的根便是最小的元素，因此peek操作就是傳回根nums[0]元素即可；
若要將nums[0]刪除，可以將末尾的元素nums[n-1]改寫nums[0],然後將堆得size = size-1，呼叫siftDown(0)調整堆。時間複雜度為logn。

peek
同上

delete(i)

刪除堆中位置為i的節點，涉及到兩個函式siftUp和siftDown，時間複雜度為logn,具體步驟是，

• 將元素last改寫元素i，然後siftDown

• 檢查是否需要siftUp

註意到堆的刪除操作，如果是刪除堆的根節點，則不用考慮執行siftUp的操作；若刪除的是堆的非根節點，則要視情況決定是siftDown還是siftUp操作，兩個操作是互斥的。

public int delete(int i) {

int key = nums[i];

//將last元素移動過來，先siftDown; 再視情況考慮是否siftUp

int last = nums[i] = nums[size–1];

size—;

siftDown(i);

//check #i的node的鍵值是否確實發生改變（是否siftDown操作生效）,若發生改變，則ok,否則為確保堆性質，則需要siftUp

if (i < size && nums[i] == last) {

System.out.println(“delete siftUp”);

siftUp(i);

}

     return key;

}

case 1 :

刪除中間節點i21，將最後一個節點複製過來；

由於沒有進行siftDown操作，節點i的值仍然為6，因此為確保堆的性質，執行siftUp操作；

case 2

刪除中間節點i，將值為11的節點複製過來，執行siftDown操作；

由於執行siftDown操作後，節點i的值不再是11，因此就不用再執行siftUp操作了，因為堆的性質在siftDown操作生效後已經得到了保持。

---

可以看出，堆的基本操作都依賴於兩個核心的函式siftUp和siftDown；較為完整的Heap程式碼如下：

class Heap {

private final static int N = 100; //default size

private int[] nums;

private int size;

public Heap(int[] nums) {

this.nums = nums;

this.size = nums.length;

heapify(this.nums);

}

public Heap() {

this.nums = new int[N];

}

/**

* heapify an array, O(n)

* @param nums An array to be heapified.

*/

private void heapify(int[] nums) {

for (int j = (size – 1) >> 1; j >= 0; j—)

siftDown(j);

}

/**

* append x to heap

* O(logn)

* @param x

* @return

*/

public int insert(int x) {

if (size >= this.nums.length)

expandSpace();

size += 1;

nums[size–1] = x;

siftUp(size–1);

return x;

}

/**

* delete an element located in i position.

* O(logn)

* @param i

* @return

*/

public int delete(int i) {

rangeCheck(i);

int key = nums[i];

//將last元素改寫過來,先siftDown; 再視情況考慮是否siftUp;

int last = nums[i] = nums[size–1];

size—;

siftDown(i);

//check #i的node的鍵值是否確實發生改變,若發生改變，則ok,否則為確保堆性質，則需要siftUp;

if (i < size && nums[i] == last)

siftUp(i);

return key;

}

/**

* remove the root of heap, return it’s value, and adjust heap to maintain the heap’s property.

* O(logn)

* @return

*/

public int extractMin() {

rangeCheck(0);

int key = nums[0], last = nums[size–1];

nums[0] = last;

size—;

siftDown(0);

return key;

}

/**

* return an element’s index, if not exists, return -1;

* O(n)

* @param x

* @return

*/

public int search(int x) {

for (int i = 0; i < size; i++)

if (nums[i] == x)

return i;

return –1;

}

/**

* return but does not remove the root of heap.

* O(1)

* @return

*/

public int peek() {

rangeCheck(0);

return nums[0];

}

private void siftUp(int i) {

int key = nums[i];

for (; i > 0😉 {

int p = (i – 1) >>> 1;

if (nums[p] <= key)

break;

nums[i] = nums[p];

i = p;

}

nums[i] = key;

}

private void siftDown(int i) {

int key = nums[i];

for (;i < size / 2😉 {

int child = (i << 1) + 1;

if (child + 1 < size && nums[child] > nums[child+1])

child++;

if (key <= nums[child])

break;

nums[i] = nums[child];

i = child;

}

nums[i] = key;

}

private void rangeCheck(int i) {

if (!(0 <= i && i < size))

throw new RuntimeException(“Index is out of boundary”);

}

private void expandSpace() {

this.nums = Arrays.copyOf(this.nums, size * 2);

}

<a href=‘http://www.jobbole.com/members/wx610506454’>@Overridea>

public String toString() {

// TODO Auto-generated method stub

StringBuilder sb = new StringBuilder();

sb.append(“[“);

for (int i = 0; i < size; i++)

sb.append(String.format((i != 0 ? “, “ : “”) + “%d”, nums[i]));

sb.append(“]\n”);

return sb.toString();

}

}

2.堆的應用：堆排序

運用堆的性質，我們可以得到一種常用的、穩定的、高效的排序演演算法————堆排序。堆排序的時間複雜度為O(n*log(n))，空間複雜度為O(1)，堆排序的思想是：
對於含有n個元素的無序陣列nums, 構建一個堆(這裡是小頂堆)heap，然後執行extractMin得到最小的元素，這樣執行n次得到序列就是排序好的序列。
如果是降序排列則是小頂堆；否則利用大頂堆。

Trick

由於extractMin執行完畢後，最後一個元素last已經被移動到了root，因此可以將extractMin傳回的元素放置於最後，這樣可以得到sort in place的堆排序演演算法。

具體操作如下：

int[] n = new int[] {1,9,5,6,8,3,1,2,5,9,86};

Heap h = new Heap(n);

for (int i = 0; i < n.length; i++)

n[n.length–1–i] = h.extractMin();

當然，如果不使用前面定義的heap，則可以手動寫堆排序，由於堆排序設計到建堆和extractMin， 兩個操作都公共依賴於siftDown函式，因此我們只需要實現siftDown即可。(trick:由於建堆操作可以採用siftUp或者siftDown，而extractMin是需要siftDown操作，因此取公共部分，則採用siftDown建堆)。

這裡便於和前面統一，採用小頂堆陣列進行降序排列。

public void heapSort(int[] nums) {

int size = nums.length;

buildMinHeap(nums);

while (size != 0) {

// 交換堆頂和最後一個元素

int tmp = nums[0];

nums[0] = nums[size – 1];

nums[size – 1] = tmp;

size—;

siftDown(nums, 0, size);

}

}

 

// 建立小頂堆

private void buildMinHeap(int[] nums) {

int size = nums.length;

for (int j = size / 2 – 1; j >= 0; j—)

siftDown(nums, j, size);

}

 

private void siftDown(int[] nums, int i, int newSize) {

int key = nums[i];

while (i < newSize >>> 1) {

int leftChild = (i << 1) + 1;

int rightChild = leftChild + 1;

// 最小的孩子，比最小的孩子還小

int min = (rightChild >= newSize || nums[leftChild] < nums[rightChild]) ? leftChild : rightChild;

if (key <= nums[min])

break;

nums[i] = nums[min];

i = min;

}

nums[i] = key;

}

3.堆的應用：優先佇列

優先佇列是一種抽象的資料型別，它和堆的關係類似於，List和陣列、連結串列的關係一樣；我們常常使用堆來實現優先佇列，因此很多時候堆和優先佇列都很相似，它們只是概念上的區分。
優先佇列的應用場景十分的廣泛：
常見的應用有：

• Dijkstra’s algorithm（單源最短路問題中需要在鄰接表中找到某一點的最短鄰接邊，這可以將複雜度降低。）

• Huffman coding（貪心演演算法的一個典型例子，採用優先佇列構建最優的字首編碼樹(prefixEncodeTree)）

• Prim’s algorithm for minimum spanning tree

• Best-first search algorithms

這裡簡單介紹上述應用之一：Huffman coding。

Huffman編碼是一種變長的編碼方案，對於每一個字元，所對應的二進位制位串的長度是不一致的，但是遵守如下原則：

• 出現頻率高的字元的二進位制位串的長度小

• 不存在一個字元c的二進位制位串s是除c外任意字元的二進位制位串的字首

遵守這樣原則的Huffman編碼屬於變長編碼，可以無損的壓縮資料，壓縮後通常可以節省20%-90%的空間，具體壓縮率依賴於資料的固有結構。

Huffman編碼的實現就是要找到滿足這兩種原則的 字元-二進位制位串 對照關係，即找到最優字首碼的編碼方案（字首碼：沒有任何字元編碼後的二進位制位串是其他字元編碼後位串的字首）。
這裡我們需要用到二叉樹來表達最優字首碼，該樹稱為最優字首碼樹
一棵最優字首碼樹看起來像這樣：

演演算法思想：用一個屬性為freqeunce關鍵字的最小優先佇列Q,將當前最小的兩個元素x,y合併得到一個新元素z（z.frequence = x.freqeunce + y.frequence）,
然後插入到優先佇列中Q中，這樣執行n-1次合併後，得到一棵最優字首碼樹（這裡不討論演演算法的證明）。

一個常見的構建流程如下：

樹中指向某個節點左孩子的邊上表示位0,指向右孩子的邊上的表示位1，這樣遍歷一棵最優字首碼樹就可以得到對照表。

import java.util.Comparator;

import java.util.HashMap;

import java.util.Map;

import java.util.PriorityQueue;

 

/**

*

*                            root

*                            /   \

*                    ——— ———-

*                    |c:freq | | c:freq |

*                    ——— ———-

*

*

*/

public class HuffmanEncodeDemo {

 

public static void main(String[] args) {

// TODO Auto-generated method stub

Node[] n = new Node[6];

float[] freq = new float[] { 9, 5, 45, 13, 16, 12 };

char[] chs = new char[] { ‘e’, ‘f’, ‘a’, ‘b’, ‘d’, ‘c’ };

HuffmanEncodeDemo demo = new HuffmanEncodeDemo();

Node root = demo.buildPrefixEncodeTree(n, freq, chs);

Map<Character, String> collector = new HashMap<>();

StringBuilder sb = new StringBuilder();

demo.tranversalPrefixEncodeTree(root, collector, sb);

System.out.println(collector);

String s = “abcabcefefefeabcdbebfbebfbabc”;

StringBuilder sb1 = new StringBuilder();

for (char c : s.toCharArray()) {

sb1.append(collector.get(c));

}

System.out.println(sb1.toString());

}

 

public Node buildPrefixEncodeTree(Node[] n, float[] freq, char[] chs) {

PriorityQueue<Node> pQ = new PriorityQueue<>(new Comparator<Node>() {

public int compare(Node o1, Node o2) {

return o1.item.freq > o2.item.freq ? 1 : o1.item.freq == o2.item.freq ? 0 : –1;

};

});

Node e = null;

for (int i = 0; i < chs.length; i++) {

n[i] = e = new Node(null, null, new Item(chs[i], freq[i]));

pQ.add(e);

}

 

for (int i = 0; i < n.length – 1; i++) {

Node x = pQ.poll(), y = pQ.poll();

Node z = new Node(x, y, new Item(‘$’, x.item.freq + y.item.freq));

pQ.add(z);

}

return pQ.poll();

}

/**

* tranversal  

* @param root

* @param collector

* @param sb

*/

public void tranversalPrefixEncodeTree(Node root, Map<Character, String> collector, StringBuilder sb) {

// leaf node

if (root.left == null && root.right == null) {

collector.put(root.item.c, sb.toString());

return;

}

Node left = root.left, right = root.right;

tranversalPrefixEncodeTree(left, collector, sb.append(0));

sb.delete(sb.length() – 1, sb.length());

tranversalPrefixEncodeTree(right, collector, sb.append(1));

sb.delete(sb.length() – 1, sb.length());

}

}

 

class Node {

public Node left, right;

public Item item;

 

public Node(Node left, Node right, Item item) {

super();

this.left = left;

this.right = right;

this.item = item;

}

 

}

 

class Item {

public char c;

public float freq;

 

public Item(char c, float freq) {

super();

this.c = c;

this.freq = freq;

}

}

輸出如下：

{a=0, b=101, c=100, d=111, e=1101, f=1100}

010110001011001101110011011100110111001101010110011110111011011100101110110111001010101100

4 堆的應用：海量實數中（一億級別以上）找到TopK（一萬級別以下）的數集合。

• A:通常遇到找一個集合中的TopK問題，想到的便是排序，因為常見的排序演演算法例如快排算是比較快了，然後再取出K個TopK數，時間複雜度為O(nlogn)，當n很大的時候這個時間複雜度還是很大的；

• B:另一種思路就是打擂臺的方式,每個元素與K個待選元素比較一次，時間複雜度很高：O(k*n)，此方案明顯遜色於前者。

對於一億資料來說，A方案大約是26.575424*n；

• C:由於我們只需要TopK，因此不需要對所有資料進行排序，可以利用堆得思想，維護一個大小為K的小頂堆，然後依次遍歷每個元素e, 若元素e大於堆頂元素root，則刪除root，將e放在堆頂，然後調整，時間複雜度為logK；若小於或等於，則考察下一個元素。這樣遍歷一遍後，最小堆裡面保留的數就是我們要找的topK，整體時間複雜度為O(k+n*logk)約等於O(n*logk)，大約是13.287712*n（由於k與n數量級差太多），這樣時間複雜度下降了約一半。

A、B、C三個方案中，C通常是優於B的，因為logK通常是小於k的，當K和n的數量級相差越大，這種方式越有效。

以下為具體操作：

import java.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.io.UnsupportedEncodingException;

import java.util.Arrays;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class TopKNumbersInMassiveNumbersDemo {

 

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] topK = new int[]{50001,50002,50003,50004,50005};

genData(1000 * 1000 * 1000, 500, topK);

long t = System.currentTimeMillis();

findTopK(topK.length);

System.out.println(String.format(“cost:%fs”, (System.currentTimeMillis() – t) * 1.0 / 1000));

}

public static void genData(int N, int maxRandomNumer, int[] topK) {

File f = new File(“data.txt”);

int k = topK.length;

Set<Integer> index = new TreeSet<>();

for (;;) {

index.add((int)(Math.random() * N));

if (index.size() == k)

break;

}

System.out.println(index);

int j = 0;

try {

PrintWriter pW = new PrintWriter(f, “UTF-8”);

for (int i = 0; i < N; i++)

if(!index.contains(i))

pW.println((int)(Math.random() * maxRandomNumer));

else

pW.println(topK[j++]);

pW.flush();

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

} catch (UnsupportedEncodingException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

public static void findTopK(int k) {

int[] nums = new int[k];

//read

File f = new File(“data.txt”);

try {

Scanner scanner = new Scanner(f);

for (int j = 0;j < k; j++)

nums[j] = scanner.nextInt();

heapify(nums);

//core

while (scanner.hasNextInt()) {

int a = scanner.nextInt();

if (a <= nums[0])

continue;

else {

nums[0] = a;

siftDown(0, k, nums);

}

}

System.out.println(Arrays.toString(nums));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

//O(n), minimal heap

public static void heapify(int[] nums) {

int size = nums.length;

for (int j = (size – 1) >> 1; j >= 0; j—)

siftDown(j, size, nums);

}

private static void siftDown(int i, int n, int[] nums) {

int key = nums[i];

for (;i < (n >>> 1);) {

int child = (i << 1) + 1;

if (child + 1 < n && nums[child] > nums[child+1])

child++;

if (key <= nums[child])

break;

nums[i] = nums[child];

i = child;

}

nums[i] = key;

}

}

ps:大致測試了一下，10億個數中找到top5需要140秒左右，應該是很快了。

5 總結

• 堆是基於樹的滿足一定約束的重要資料結構，存在許多變體例如二叉堆、二項式堆、斐波那契堆（很高效）等。

• 堆的幾個基本操作都依賴於兩個重要的函式siftUp和siftDown，堆的insert通常是在堆尾插入新元素並siftUp調整堆，而extractMin是在
  刪除堆頂元素，然後將最後一個元素放置堆頂並呼叫siftDown調整堆。

• 二叉堆是常用的一種堆，其是一棵二叉樹；由於二叉樹良好的性質，因此常常採用陣列來儲存堆。
  堆得基本操作的時間複雜度如下表所示：

heapify	insert	peek	extractMin	delete(i)
O(n)	O(logn)	O(1)	O(logn)	O(logn)

• 二叉堆通常被用來實現堆排序演演算法，堆排序可以sort in place，堆排序的時間複雜度的上界是O(nlogn)，是一種很優秀的排序演演算法。由於存在相同鍵值的兩個元素處於兩棵子樹中，而兩個元素的順序可能會在後續的堆調整中發生改變，因此堆排序不是穩定的。降序排序需要建立小頂堆，升序排序需要建立大頂堆。

• 堆是實現抽象資料型別優先佇列的一種方式，優先佇列有很廣泛的應用，例如Huffman編碼中使用優先佇列利用貪心演演算法構建最優字首編碼樹。

• 堆的另一個應用就是在海量資料中找到TopK個數，思想是維護一個大小為K的二叉堆，然後不斷地比較堆頂元素，判斷是否需要執行替換對頂元素的操作，採用
  此方法的時間複雜度為n*logk，當k和n的數量級差距很大的時候，這種方式是很有效的方法。

6 references

[1] https://en.wikipedia.org/wiki/Heap_(data_structure))

[2] https://en.wikipedia.org/wiki/Heapsort

[3] https://en.wikipedia.org/wiki/Priority_queue

[4] https://www.cnblogs.com/swiftma/p/6006395.html

[5] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein.演演算法導論[M].北京:機械工業出版社,2015:245-249

[6] Jon Bentley.程式設計珠璣[M].北京:人民郵電出版社,2015:161-174

覺得本文有幫助？請分享給更多人

關註「演演算法愛好者」，修煉程式設計內功