堆和堆的應(yīng)用：堆排序和優(yōu)先隊(duì)列

1.堆

堆(Heap))是一種重要的數(shù)據(jù)結(jié)構(gòu)，是實(shí)現(xiàn)優(yōu)先隊(duì)列(Priority Queues)首選的數(shù)據(jù)結(jié)構(gòu)。由于堆有很多種變體，包括二項(xiàng)式堆、斐波那契堆等，但是這里只考慮最常見的就是二叉堆（以下簡稱堆）。

堆是一棵滿足一定性質(zhì)的二叉樹，具體的講堆具有如下性質(zhì)：父節(jié)點(diǎn)的鍵值總是不大于它的孩子節(jié)點(diǎn)的鍵值（小頂堆）, 堆可以分為小頂堆和大頂堆，這里以小頂堆為例，其主要包含的操作有：

insert()

extractMin

peek(findMin)

delete(i)

由于堆是一棵形態(tài)規(guī)則的二叉樹，因此堆的父節(jié)點(diǎn)和孩子節(jié)點(diǎn)存在如下關(guān)系：

設(shè)父節(jié)點(diǎn)的編號(hào)為i, 則其左孩子節(jié)點(diǎn)的編號(hào)為2*i+1, 右孩子節(jié)點(diǎn)的編號(hào)為2*i+2設(shè)孩子節(jié)點(diǎn)的編號(hào)為i, 則其父節(jié)點(diǎn)的編號(hào)為(i-1)/2

由于二叉樹良好的形態(tài)已經(jīng)包含了父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的關(guān)系信息，因此就可以不使用鏈表而簡單的使用數(shù)組來存儲(chǔ)堆。

要實(shí)現(xiàn)堆的基本操作，涉及到的兩個(gè)關(guān)鍵的函數(shù)

siftUp(i, x)： 將位置i的元素x向上調(diào)整，以滿足堆得性質(zhì)，常常是用于insert后，用于調(diào)整堆；

siftDown(i, x)：同理，常常是用于delete(i)后，用于調(diào)整堆；

具體的操作如下：

privatevoidsiftUp(inti){

intkey = nums[i];

for(;i > 0;){

intp = (i - 1) >>> 1;

if(nums[p] <= key)

break;

nums[i] = nums[p];

i = p;

}

nums[i] = key;

}

privatevoidsiftDown(inti){

intkey = nums[i];

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

intchild = (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不停的在父節(jié)點(diǎn)和子節(jié)點(diǎn)之間比較、交換；在不超過logn的時(shí)間復(fù)雜度就可以完成一次操作。

有了這兩個(gè)基本的函數(shù)，就可以實(shí)現(xiàn)上述提及的堆的基本操作。

首先是如何建堆，實(shí)現(xiàn)建堆操作有兩個(gè)思路:

一個(gè)是不斷地insert（insert后調(diào)用的是siftUp）

另一個(gè)將原始數(shù)組當(dāng)成一個(gè)需要調(diào)整的堆，然后自底向上地在每個(gè)位置i調(diào)用siftDown(i)，完成后我們就可以得到一個(gè)滿足堆性質(zhì)的堆。這里考慮后一種思路：

通常堆的insert操作是將元素插入到堆尾，由于新元素的插入可能違反堆的性質(zhì)，因此需要調(diào)用siftUp操作自底向上調(diào)整堆；堆移除堆頂元素操作是將堆頂元素刪除，然后將堆最后一個(gè)元素放置在堆頂，接著執(zhí)行siftDown操作，同理替換堆頂元素也是相同的操作。

建堆

// 建立小頂堆

privatevoidbuildMinHeap(int[]nums){

intsize = nums.length;

for(intj = size / 2 - 1;j >= 0;j--)

siftDown(nums,j,size);

}

那么建堆操作的時(shí)間復(fù)雜度是多少呢？答案是O(n)。雖然siftDown的操作時(shí)間是logn，但是由于高度在遞減的同時(shí)，每一層的節(jié)點(diǎn)數(shù)量也在成倍減少，最后通過數(shù)列錯(cuò)位相減可以得到時(shí)間復(fù)雜度是O(n)。

extractMin由于堆的固有性質(zhì)，堆的根便是最小的元素，因此peek操作就是返回根nums[0]元素即可；若要將nums[0]刪除，可以將末尾的元素nums[n-1]覆蓋nums[0],然后將堆得size = size-1，調(diào)用siftDown(0)調(diào)整堆。時(shí)間復(fù)雜度為logn。

peek同上

delete(i)

刪除堆中位置為i的節(jié)點(diǎn)，涉及到兩個(gè)函數(shù)siftUp和siftDown，時(shí)間復(fù)雜度為logn,具體步驟是，

將元素last覆蓋元素i，然后siftDown

檢查是否需要siftUp

注意到堆的刪除操作，如果是刪除堆的根節(jié)點(diǎn)，則不用考慮執(zhí)行siftUp的操作；若刪除的是堆的非根節(jié)點(diǎn)，則要視情況決定是siftDown還是siftUp操作，兩個(gè)操作是互斥的。

publicintdelete(inti){

intkey = nums[i];

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

intlast = nums[i] = nums[size-1];

size--;

siftDown(i);

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

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

System.out.println("delete siftUp");

siftUp(i);

}

returnkey;

}

case 1 :

刪除中間節(jié)點(diǎn)i21，將最后一個(gè)節(jié)點(diǎn)復(fù)制過來；

由于沒有進(jìn)行siftDown操作，節(jié)點(diǎn)i的值仍然為6，因此為確保堆的性質(zhì)，執(zhí)行siftUp操作；

case 2

刪除中間節(jié)點(diǎn)i，將值為11的節(jié)點(diǎn)復(fù)制過來，執(zhí)行siftDown操作；

由于執(zhí)行siftDown操作后，節(jié)點(diǎn)i的值不再是11，因此就不用再執(zhí)行siftUp操作了，因?yàn)槎训男再|(zhì)在siftDown操作生效后已經(jīng)得到了保持。

可以看出，堆的基本操作都依賴于兩個(gè)核心的函數(shù)siftUp和siftDown；較為完整的Heap代碼如下：

classHeap{

privatefinalstaticintN = 100;//default size

privateint[]nums;

privateintsize;

publicHeap(int[]nums){

this.nums = nums;

this.size = nums.length;

heapify(this.nums);

}

publicHeap(){

this.nums = newint[N];

}

/**

* heapify an array, O(n)

* @param nums An array to be heapified.

*/

privatevoidheapify(int[]nums){

for(intj = (size - 1) >> 1;j >= 0;j--)

siftDown(j);

}

/**

* append x to heap

* O(logn)

* @param x

* @return

*/

publicintinsert(intx){

if(size >= this.nums.length)

expandSpace();

size += 1;

nums[size-1] = x;

siftUp(size-1);

returnx;

}

/**

* delete an element located in i position.

* O(logn)

* @param i

* @return

*/

publicintdelete(inti){

rangeCheck(i);

intkey = nums[i];

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

intlast = nums[i] = nums[size-1];

size--;

siftDown(i);

//check #i的node的鍵值是否確實(shí)發(fā)生改變,若發(fā)生改變，則ok,否則為確保堆性質(zhì)，則需要siftUp;

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

siftUp(i);

returnkey;

}

/**

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

* O(logn)

* @return

*/

publicintextractMin(){

rangeCheck(0);

intkey = nums[0],last = nums[size-1];

nums[0] = last;

size--;

siftDown(0);

returnkey;

}

/**

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

* O(n)

* @param x

* @return

*/

publicintsearch(intx){

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

if(nums[i] == x)

returni;

return -1;

}

/**

* return but does not remove the root of heap.

* O(1)

* @return

*/

publicintpeek(){

rangeCheck(0);

returnnums[0];

}

privatevoidsiftUp(inti){

intkey = nums[i];

for(;i > 0;){

intp = (i - 1) >>> 1;

if(nums[p] <= key)

break;

nums[i] = nums[p];

i = p;

}

nums[i] = key;

}

privatevoidsiftDown(inti){

intkey = nums[i];

for(;i < size / 2;){

intchild = (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;

}

privatevoidrangeCheck(inti){

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

thrownewRuntimeException("Index is out of boundary");

}

privatevoidexpandSpace(){

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

}

@Override

publicStringtoString(){

// TODO Auto-generated method stub

StringBuilder sb = newStringBuilder();

sb.append("[");

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

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

sb.append("] ");

returnsb.toString();

}

}

2.堆的應(yīng)用：堆排序

運(yùn)用堆的性質(zhì)，我們可以得到一種常用的、穩(wěn)定的、高效的排序算法————堆排序。堆排序的時(shí)間復(fù)雜度為O(n*log(n))，空間復(fù)雜度為O(1)，堆排序的思想是：對(duì)于含有n個(gè)元素的無序數(shù)組nums, 構(gòu)建一個(gè)堆(這里是小頂堆)heap，然后執(zhí)行extractMin得到最小的元素，這樣執(zhí)行n次得到序列就是排序好的序列。如果是降序排列則是小頂堆；否則利用大頂堆。

Trick

由于extractMin執(zhí)行完畢后，最后一個(gè)元素last已經(jīng)被移動(dòng)到了root，因此可以將extractMin返回的元素放置于最后，這樣可以得到sort in place的堆排序算法。

具體操作如下：

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

Heaph = newHeap(n);

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

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

當(dāng)然，如果不使用前面定義的heap，則可以手動(dòng)寫堆排序，由于堆排序設(shè)計(jì)到建堆和extractMin， 兩個(gè)操作都公共依賴于siftDown函數(shù)，因此我們只需要實(shí)現(xiàn)siftDown即可。(trick:由于建堆操作可以采用siftUp或者siftDown，而extractMin是需要siftDown操作，因此取公共部分，則采用siftDown建堆)。

這里便于和前面統(tǒng)一，采用小頂堆數(shù)組進(jìn)行降序排列。

publicvoidheapSort(int[]nums){

intsize = nums.length;

buildMinHeap(nums);

while(size != 0){

// 交換堆頂和最后一個(gè)元素

inttmp = nums[0];

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

nums[size - 1] = tmp;

size--;

siftDown(nums,0,size);

}

}

// 建立小頂堆

privatevoidbuildMinHeap(int[]nums){

intsize = nums.length;

for(intj = size / 2 - 1;j >= 0;j--)

siftDown(nums,j,size);

}

privatevoidsiftDown(int[]nums,inti,intnewSize){

intkey = nums[i];

while(i < newSize >>> 1){

intleftChild = (i << 1) + 1;

intrightChild = leftChild + 1;

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

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

if(key <= nums[min])

break;

nums[i] = nums[min];

i = min;

}

nums[i] = key;

}

3.堆的應(yīng)用：優(yōu)先隊(duì)列

優(yōu)先隊(duì)列是一種抽象的數(shù)據(jù)類型，它和堆的關(guān)系類似于，List和數(shù)組、鏈表的關(guān)系一樣；我們常常使用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列，因此很多時(shí)候堆和優(yōu)先隊(duì)列都很相似，它們只是概念上的區(qū)分。優(yōu)先隊(duì)列的應(yīng)用場景十分的廣泛：常見的應(yīng)用有：

Dijkstra’s algorithm（單源最短路問題中需要在鄰接表中找到某一點(diǎn)的最短鄰接邊，這可以將復(fù)雜度降低。）

Huffman coding（貪心算法的一個(gè)典型例子，采用優(yōu)先隊(duì)列構(gòu)建最優(yōu)的前綴編碼樹(prefixEncodeTree)）

Prim’s algorithm for minimum spanning tree

Best-first search algorithms

這里簡單介紹上述應(yīng)用之一：Huffman coding。

Huffman編碼是一種變長的編碼方案，對(duì)于每一個(gè)字符，所對(duì)應(yīng)的二進(jìn)制位串的長度是不一致的，但是遵守如下原則：

出現(xiàn)頻率高的字符的二進(jìn)制位串的長度小

不存在一個(gè)字符c的二進(jìn)制位串s是除c外任意字符的二進(jìn)制位串的前綴

遵守這樣原則的Huffman編碼屬于變長編碼，可以無損的壓縮數(shù)據(jù)，壓縮后通?？梢怨?jié)省20%-90%的空間，具體壓縮率依賴于數(shù)據(jù)的固有結(jié)構(gòu)。

Huffman編碼的實(shí)現(xiàn)就是要找到滿足這兩種原則的字符-二進(jìn)制位串對(duì)照關(guān)系，即找到最優(yōu)前綴碼的編碼方案（前綴碼：沒有任何字符編碼后的二進(jìn)制位串是其他字符編碼后位串的前綴）。這里我們需要用到二叉樹來表達(dá)最優(yōu)前綴碼，該樹稱為最優(yōu)前綴碼樹一棵最優(yōu)前綴碼樹看起來像這樣：

算法思想：用一個(gè)屬性為freqeunce關(guān)鍵字的最小優(yōu)先隊(duì)列Q,將當(dāng)前最小的兩個(gè)元素x,y合并得到一個(gè)新元素z（z.frequence = x.freqeunce + y.frequence）,然后插入到優(yōu)先隊(duì)列中Q中，這樣執(zhí)行n-1次合并后，得到一棵最優(yōu)前綴碼樹（這里不討論算法的證明）。

一個(gè)常見的構(gòu)建流程如下：

樹中指向某個(gè)節(jié)點(diǎn)左孩子的邊上表示位0,指向右孩子的邊上的表示位1，這樣遍歷一棵最優(yōu)前綴碼樹就可以得到對(duì)照表。

import java.util.Comparator;

import java.util.HashMap;

import java.util.Map;

import java.util.PriorityQueue;

/**

*

*root

*/

*--------- ----------

*|c:freq | | c:freq |

*--------- ----------

*

*

*/

publicclassHuffmanEncodeDemo{

publicstaticvoidmain(String[]args){

// TODO Auto-generated method stub

Node[]n = newNode[6];

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

char[]chs = newchar[]{'e','f','a','b','d','c'};

HuffmanEncodeDemo demo = newHuffmanEncodeDemo();

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

Map collector = newHashMap<>();

StringBuilder sb = newStringBuilder();

demo.tranversalPrefixEncodeTree(root,collector,sb);

System.out.println(collector);

Strings = "abcabcefefefeabcdbebfbebfbabc";

StringBuilder sb1 = newStringBuilder();

for(charc : s.toCharArray()){

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

}

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

}

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

PriorityQueue pQ = newPriorityQueue<>(newComparator(){

publicintcompare(Node o1,Node o2){

returno1.item.freq > o2.item.freq?1 : o1.item.freq == o2.item.freq?0 : -1;

};

});

Nodee = null;

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

n[i] = e = newNode(null,null,newItem(chs[i],freq[i]));

pQ.add(e);

}

for(inti = 0;i < n.length - 1;i++){

Nodex = pQ.poll(),y = pQ.poll();

Nodez = newNode(x,y,newItem('$',x.item.freq + y.item.freq));

pQ.add(z);

}

returnpQ.poll();

}

/**

* tranversal

* @param root

* @param collector

* @param sb

*/

publicvoidtranversalPrefixEncodeTree(Node root,Map 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());

}

}

classNode{

publicNode left,right;

publicItem item;

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

super();

this.left = left;

this.right = right;

this.item = item;

}

}

classItem{

publiccharc;

publicfloatfreq;

publicItem(charc,floatfreq){

super();

this.c = c;

this.freq = freq;

}

}

輸出如下：

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

010110001011001101110011011100110111001101010110011110111011011100101110110111001010101100

4 堆的應(yīng)用：海量實(shí)數(shù)中（一億級(jí)別以上）找到TopK（一萬級(jí)別以下）的數(shù)集合。

A:通常遇到找一個(gè)集合中的TopK問題，想到的便是排序，因?yàn)槌Ｒ姷呐判蛩惴ɡ缈炫潘闶潜容^快了，然后再取出K個(gè)TopK數(shù)，時(shí)間復(fù)雜度為O(nlogn)，當(dāng)n很大的時(shí)候這個(gè)時(shí)間復(fù)雜度還是很大的；

B:另一種思路就是打擂臺(tái)的方式,每個(gè)元素與K個(gè)待選元素比較一次，時(shí)間復(fù)雜度很高：O(k*n)，此方案明顯遜色于前者。

對(duì)于一億數(shù)據(jù)來說，A方案大約是26.575424*n；

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

A、B、C三個(gè)方案中，C通常是優(yōu)于B的，因?yàn)閘ogK通常是小于k的，當(dāng)K和n的數(shù)量級(jí)相差越大，這種方式越有效。

以下為具體操作：

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;

publicclassTopKNumbersInMassiveNumbersDemo{

publicstaticvoidmain(String[]args){

// TODO Auto-generated method stub

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

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

longt = System.currentTimeMillis();

findTopK(topK.length);

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

}

publicstaticvoidgenData(intN,intmaxRandomNumer,int[]topK){

Filef = newFile("data.txt");

intk = topK.length;

Set index = newTreeSet<>();

for(;;){

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

if(index.size() == k)

break;

}

System.out.println(index);

intj = 0;

try{

PrintWriter pW = newPrintWriter(f,"UTF-8");

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

if(!index.contains(i))

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

else

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

pW.flush();

}catch(FileNotFoundExceptione){

// TODO Auto-generated catch block

e.printStackTrace();

}catch(UnsupportedEncodingExceptione){

// TODO Auto-generated catch block

e.printStackTrace();

}

}

publicstaticvoidfindTopK(intk){

int[]nums = newint[k];

//read

Filef = newFile("data.txt");

try{

Scanner scanner = newScanner(f);

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

nums[j] = scanner.nextInt();

heapify(nums);

//core

while(scanner.hasNextInt()){

inta = scanner.nextInt();

if(a <= nums[0])

continue;

else{

nums[0] = a;

siftDown(0,k,nums);

}

}

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

}catch(FileNotFoundExceptione){

// TODO Auto-generated catch block

e.printStackTrace();

}

}

//O(n), minimal heap

publicstaticvoidheapify(int[]nums){

intsize = nums.length;

for(intj = (size - 1) >> 1;j >= 0;j--)

siftDown(j,size,nums);

}

privatestaticvoidsiftDown(inti,intn,int[]nums){

intkey = nums[i];

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

intchild = (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億個(gè)數(shù)中找到top5需要140秒左右，應(yīng)該是很快了。

5 總結(jié)

堆是基于樹的滿足一定約束的重要數(shù)據(jù)結(jié)構(gòu)，存在許多變體例如二叉堆、二項(xiàng)式堆、斐波那契堆（很高效）等。

堆的幾個(gè)基本操作都依賴于兩個(gè)重要的函數(shù)siftUp和siftDown，堆的insert通常是在堆尾插入新元素并siftUp調(diào)整堆，而extractMin是在刪除堆頂元素，然后將最后一個(gè)元素放置堆頂并調(diào)用siftDown調(diào)整堆。

二叉堆是常用的一種堆，其是一棵二叉樹；由于二叉樹良好的性質(zhì)，因此常常采用數(shù)組來存儲(chǔ)堆。堆得基本操作的時(shí)間復(fù)雜度如下表所示：

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

二叉堆通常被用來實(shí)現(xiàn)堆排序算法，堆排序可以sort in place，堆排序的時(shí)間復(fù)雜度的上界是O(nlogn)，是一種很優(yōu)秀的排序算法。由于存在相同鍵值的兩個(gè)元素處于兩棵子樹中，而兩個(gè)元素的順序可能會(huì)在后續(xù)的堆調(diào)整中發(fā)生改變，因此堆排序不是穩(wěn)定的。降序排序需要建立小頂堆，升序排序需要建立大頂堆。

堆是實(shí)現(xiàn)抽象數(shù)據(jù)類型優(yōu)先隊(duì)列的一種方式，優(yōu)先隊(duì)列有很廣泛的應(yīng)用，例如Huffman編碼中使用優(yōu)先隊(duì)列利用貪心算法構(gòu)建最優(yōu)前綴編碼樹。

堆的另一個(gè)應(yīng)用就是在海量數(shù)據(jù)中找到TopK個(gè)數(shù)，思想是維護(hù)一個(gè)大小為K的二叉堆，然后不斷地比較堆頂元素，判斷是否需要執(zhí)行替換對(duì)頂元素的操作，采用此方法的時(shí)間復(fù)雜度為n*logk，當(dāng)k和n的數(shù)量級(jí)差距很大的時(shí)候，這種方式是很有效的方法。

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.算法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2015:245-249

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

●本文編號(hào)591，以后想閱讀這篇文章直接輸入591即可

●輸入m獲取文章目錄