数据结构:堆和败者树的区别是什么?
一道經典的面試題
如何從N個數中選出最大(小)的n個數?
這個問題解法可以移步我的另一篇博客:
《海量數據處理:如何從10億個數中,找出最大的10000個數?(top K問題)》https://hanquan.blog.csdn.net/article/details/108277388
本文對一些解法進行討論。
Naive 方法:
首先,我們假設,n和N都是內存可容納的,也就是說N個數可以一次load到內存里存放在數組里(如果非要存在鏈表估計又是另一個challenging的問題了)。從最簡單的情況開始,如果n=1,那么沒有任何疑惑,必須要進行N-1次的比較才能得到最大的那個數,直接遍歷N個數就可以了。如果n=2呢?當然,可以直接遍歷2遍N數組,第一遍得到最大數max1,但是在遍歷第二遍求第二大數max2的時候,每次都要判斷從N所取的元素的下標不等于max1的下標,這樣會大大增加比較次數。對此有一個解決辦法,可以以max1為分割點將N數組分成前后兩部分,然后分別遍歷這兩部分得到兩個“最大數”,然后二者取一得到max2。
也可以遍歷一遍就解決此問題,首先維護兩個元素max1,max2(max1>=max2),取到N中的一個數以后,先和max1比,如果比max1大(則肯定比max2大),直接替換max1,否則再和max2比較確定是否替換max2。采用類似的方法,對于n=2,3,4……一樣可以處理。這樣的算法時間復雜度為O(nN)。當n越來越大的時候(不可能超過N/2,否則可以變成是找N-n個最小的數的對偶問題),這個算法的效率會越來越差。但是在n比較小的時候(具體多小不好說),這個算法由于簡單,不存在遞歸調用等系統損耗,實際效率應該很不錯.
堆:
當n較大的時候,采用什么算法呢?首先我們分析上面的算法,當從N中取出一個新的數m的時候,它需要依次和max1,max2,max3……max n比較,一直找到一個比m小的max x,就用m來替換max x,平均比較次數是n/2。可不可以用更少的比較次數來實現替換呢?最直觀的方法是,也就是網上文章比較推崇的堆。堆有這么一些好處:1.它是一個完全二叉樹,樹的深度是相同節點的二叉樹中最少的,維護效率較高;2.它可以通過數組來實現,而且父節點p與左右子節l,r點的數組下標的關系是s[l] = 2s[p]+1和s[r] = 2s[p]+2。在計算機中2*s[p]這樣的運算可以用一個左移1位操作來實現,十分高效。再加上數組可以隨機存取,效率也很高。3.堆的Extract操作,也就是將堆頂拿走并重新維護堆的時間復雜度是O(logn),這里n是堆的大小。
具體到我們的問題,如何具體實現呢?首先,開辟一個大小為n的數組區A,從N中讀入n個數填入到A中,然后將A維護成一個小頂堆(即堆頂A[0]中存放的是A中最小的數)。然后從N中取出下一個數,即第n+1個數m,將m與堆頂A[0]比較,如果m<=A[0],直接丟棄m。否則應該用m替換A[0]。但此時A的堆特性可能已被破壞,應該重新維護堆:從A[0]開始,將A[0]與左右子節點分別比較(特別注意,這里需要比較“兩次”才能確定最大數,在后面我會根據這個來和“敗者樹”比較),如果A[0]比左右子節點都小,則堆特性能夠保證,勿需繼續,否則如左(右)節點最大,則將A[0]與左(右)節點交換,并繼續維護左(右)子樹。依次執行,直到遍歷完N,堆中保留的n個數就是N中最大的n個數。這都是堆排序的基本知識,唯一的trick就是維護一個小頂堆,而不是大頂堆。不明白的稍微想一下。維護一次堆的時間復雜度為O(logn),總體的復雜度是O(Nlogn)這樣一來,比起上面的O(nN),當n足夠大時,堆的效率肯定是要高一些的。當然,直接對N數組建堆,然后提取n次堆頂就能得到結果,而且其復雜度是O(nlogN),當n不是特別小的時候這樣會快很多。但是對于online數據就沒辦法了,比如N不能一次load進內存,甚至是一個流,根本不知道N是多少。
敗者樹:
有沒有別的算法呢?我先來說一說敗者樹(loser tree)。
也許有些人對loser tree不是很了解,其實它是一個比較經典的外部排序方法,也就是有x個已經排序好的文件,將其歸并為一個有序序列。敗者樹的思想咋一看有些繞,其實是為了減小比較次數。
首先簡單介紹一下敗者樹:敗者樹的葉子節點是數據節點,然后兩兩分組(如果節點總數不是2的冪,可以用類似完全樹的結構構成樹),內部節點用來記錄左右子樹的優勝者中的“敗者”(注意記錄的是輸的那一方),而優勝者則往上傳遞繼續比較,一直到根節點。
如果我們的優勝者是兩個數中較小的數,則根節點記錄的是最后一次比較中的“敗者”,也就是所有葉子節點中第二小的那個數,而最小的那個數記錄在一個獨立的變量中。這里要注意,內部節點不但要記錄敗者的數值,還要記錄對應的葉子節點。
如果是用鏈表構成的樹,則內部節點需要有指針指向葉子節點。這里可以有一個trick,就是內部節點只記錄“敗者”對應的葉子節點,具體的數值可以在需要的時候間接訪問(這一方法在用數組來實現敗者樹時十分有用,后面我會講到)。
關鍵的來了,當把最小值輸出后,最小值所對應的葉子節點需要變成一個新的數(或者改為無窮大,在文件歸并的時候表示文件已讀完)。
接下來維護敗者樹,從更新的葉子節點網上,依次與內部節點比較,將“敗者”更新,勝者往上繼續比較。由于更新節點占用的是之前的最小值的葉子節點,它往上一直到根節點的路徑與之前的最小值的路徑是完全相同的。內部節點記錄的“敗者”雖然稱為“敗者”,但卻是其所在子樹中最小的數。也就是說,只要與“敗者”比較得到的勝者,就是該子樹中最小的那個數(這里講得有點繞了,看不明白的還是找本書看吧,對照著圖比較容易理解)。
注:也可以直接對N構建敗者樹,但是敗者樹用數組實現時不能像堆一樣進行增量維護,當葉子節點的個數變動時需要完全重新構建整棵樹。為了方便比較堆和敗者樹的性能,后面的分析都是對n個數構建的堆和敗者樹來分析的。
總而言之,敗者樹在進行維護的時候,比較次數是logn+1。
與堆不同的是,敗者樹是從下往上維護,每上一層,只需要和敗者節點比較“一次”即可。而堆在維護的時候是從上往下,每下一層,需要和左右子節點都比較,需要比較兩次。從這個角度,敗者樹比堆更優一些。
但是,請注意但是,敗者樹每一次維護,必定需要從葉子節點一直走到根節點,不可能中間停止;而堆維護時,“有可能”會在中間的某個層停止,不需要繼續往下。
這樣一來,雖然每一層敗者樹需要的比較次數比堆少一倍,但是走的層數堆會比敗者樹少。具體少多少,從平均意義上到底哪一個的效率會更好一些?那我就不知道了,這個分析起來有點麻煩。感興趣的人可以嘗試一下,討論討論。但是至少說明了,也許堆并非是最優的。
具體到我們的問題。類似的方法,先構建一棵有n個葉子節點的敗者樹,勝出者w是n個中最小的那一個。從N中讀入一個新的數m后,和w比較,如果比w小,直接丟棄,否則用m替換w所在的葉子節點的值,然后維護該敗者樹。依次執行,直到遍歷完N,敗者樹中保留的n個數就是N中最大的n個數。時間復雜度也是O(Nlogn)
類快速排序方法:
快速排序大家大家都不陌生了。主要思想是找一個“軸”節點,將數列交換變成兩部分,一部分全都小于等于“軸”,另一部分全都大于等于“軸”,然后對兩部分遞歸處理。其平均時間復雜度是O(NlogN)。
從中可以受到啟發,如果我們選擇的軸使得交換完的“較大”那一部分的數的個數j正好是n,不也就完成了在N個數中尋找n個最大的數的任務嗎?當然,軸也許不能選得這么恰好。可以這么分析,如果j>n,則最大的n個數肯定在這j個數中,則問題變成在這j個數中找出n個最大的數;否則如果j<n,則這j個數肯定是n個最大的數的一部分,而剩下的j-n個數在小于等于軸的那一部分中,同樣可遞歸處理。
令人愉悅的是,這個算法的平均復雜度是O(N)的。怎么樣?比堆的O(Nlogn)可能會好一些吧?!(n如果比較大肯定會好)
需要注意的是,這里的時間復雜度是平均意義上的,在最壞情況下,每次分割都分割成1:N-2,這種情況下的時間復雜度為O(n)。但是我們還有殺手锏,可以有一個在最壞情況下時間復雜度為O(N)的算法,這個算法是在分割數列的時候保證會按照比較均勻的比例分割,at least 3n/10-6。具體細節我就不再說了,感興趣的人參考算法導論(Introduction to Algorithms 第二版第九章 “Medians and Orders Statistics”)。
還是那個結論,堆不見得會是最優的。
本文快要結束了,但是還有一個問題:如果N非常大,存放在磁盤上,不能一次裝載進內存呢?怎么辦?
對于介紹的Naive方法,堆,敗者樹等等,依然適用,需要注意的就是每次從磁盤上盡量多讀一些數到內存區,然后處理完之后再讀入一批。減少IO次數,自然能夠提高效率。
而對于類快速排序方法,稍微要麻煩一些:分批讀入,假設是M個數,然后從這M個數中選出n個最大的數緩存起來,直到所有的N個數都分批處理完之后,再將各批次緩存的n個數合并起來再進行一次類快速排序得到最終的n個最大的數就可以了。
在運行過程中,如果緩存數太多,可以不斷地將多個緩存合并,保留這些緩存中最大的n個數即可。由于類快速排序的時間復雜度是O(N),這樣分批處理再合并的辦法,依然有極大的可能會比堆和敗者樹更優。當然,在空間上會占用較多的內存。
總結:
對于這個問題,我想了很多,但是覺得還有一些地方可以繼續深挖:
總結
以上是生活随笔為你收集整理的数据结构:堆和败者树的区别是什么?的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 数据结构:下列选项中,不可能是快速排序第
- 下一篇: 数据结构:排序趟数 / 比较次数与序列的