此算法應(yīng)用場(chǎng)景：
比如在各種搜索引擎中輸入關(guān)鍵詞之后與之相匹配的數(shù)據(jù)有成千上萬甚至幾百萬條择吊，但這么多的數(shù)據(jù)中其實(shí)能讓用戶真正感興趣有價(jià)值的也就這么N條，那么搜索引擎中如何把最有價(jià)值的N條數(shù)據(jù)優(yōu)先展現(xiàn)給用戶嘞？大家肯定會(huì)想到根據(jù)各種指標(biāo)比如熱度，點(diǎn)擊率等等來進(jìn)行一個(gè)排序，那么從技術(shù)角度來說我們關(guān)注的當(dāng)然就是如何排序更有效率穿剖，比如傳統(tǒng)的冒泡排序，快速排序卦溢，等等糊余，這些算法當(dāng)然都是可以的，但是這些算法的排序通常都是針對(duì)所有數(shù)據(jù)來說的既绕，當(dāng)數(shù)據(jù)量很大的時(shí)候其時(shí)間復(fù)雜度就有點(diǎn)驚人了啄刹，冒泡排序的時(shí)間復(fù)雜度為,快速排序的時(shí)間復(fù)雜度為級(jí)別的，而下面介紹的top-N算法其時(shí)間復(fù)雜度為級(jí)別的凄贩。

此算法的中心思想及實(shí)現(xiàn)過程：
一誓军、先構(gòu)建一個(gè)N個(gè)節(jié)點(diǎn)的最小頂堆二叉樹，使得父節(jié)點(diǎn)的
值比其左右孩子 的節(jié)點(diǎn)值都小疲扎，此時(shí)的二叉樹的N個(gè)節(jié)點(diǎn)中頂端節(jié)點(diǎn)的值最小昵时。
二、將N個(gè)節(jié)點(diǎn)以外的元素與根節(jié)點(diǎn)作比較如果比根節(jié)點(diǎn)大則把該元素變成新的根節(jié)點(diǎn)
三椒丧、調(diào)整新根節(jié)點(diǎn)樹使得其滿足最小頂堆二叉樹
四壹甥、重復(fù)二三過程直至遍歷所有數(shù)據(jù)
此算法只關(guān)心最有價(jià)值的N條數(shù)據(jù)忽略其他的數(shù)據(jù)原算法并沒有對(duì)這N條數(shù)據(jù)排序，為了更好的給用戶推薦內(nèi)容可以對(duì)TOP-N條數(shù)據(jù)進(jìn)行排序推薦給用戶壶熏。具體代碼實(shí)現(xiàn)如下句柠。

class TopN:
    def parent(self,n):
        #父節(jié)點(diǎn)下標(biāo)
        return int((n-1)/2)
    def left(self,n):
       # 左節(jié)點(diǎn)下標(biāo)
        return 2*n+1
    # 右節(jié)點(diǎn)下標(biāo)
    def right(self,n):
        return 2*n+2
    # 構(gòu)建小頂堆保證左右子節(jié)點(diǎn)小于其父節(jié)點(diǎn)
    def MinTopTree(self,n,data):
        for i in range(1,n):
            j = i
            while j!=0 and data[j]<data[self.parent(j)]:
                temp = 0
                temp = data[self.parent(j)]
                data[self.parent(j)] = data[j]
                data[j] = temp
                j = self.parent(j)
        return data
    # 將其他值與最小頂推比較替換data[0]值
    def ReMinTopTree(self,size,n,data):
        #data = self.MinTopTree(n,data)
        for i in range(n,size):
            if data[i]>data[0]:
              #  temp = 0
                temp = data[0]
                data[0] = data[i]
                data[i] = temp
                t = 0
                #(data[t]>data[self.right(t)] and self.right(t)<n) or (data[t]>data[self.left(t)] and data[self.left(t)]<n)這樣會(huì)越界
                #(self.left(t) < n and data[self.left(t)] < data[t]) or (self.right(t) < n and data[self.right(t)] < data[t])
                while ((self.left(t) < n and data[self.left(t)] < data[t]) or (self.right(t) < n and data[self.right(t)] < data[t])):
                    # 替換右孩子
                    if data[self.right(t)]<data[self.left(t)] and self.right(t)<n:
                        #temp = 0
                        temp = data[t]
                        data[t] = data[self.right(t)]
                        data[self.right(t)] = temp
                        t = self.right(t)
                        
                    else:
                       #替換左孩子
                        # temp = 0
                        temp = data[t]
                        data[t] = data[self.left(t)]
                        data[self.left(t)] = temp
                        t = self.left(t)
                        
        return data

top = TopN()
data = [21,1,10,17,28,19,9,30,27,6,44,20]
r1 = top.MinTopTree(7,data)
print(r1)
r2 = top.ReMinTopTree(n=7,size=12,data=r1)
print(r2)

[1, 17, 9, 21, 28, 19, 10, 30, 27, 6, 44, 20]
[19, 21, 20, 44, 28, 27, 30, 1, 9, 6, 10, 17]

github 代碼地址

https://github.com/luozekun1230/MyPyhonProgram/tree/master/Python%E5%9F%BA%E7%A1%80