TOPK 問題

TOPK 問題

描述

如從海量數(shù)字中尋找最大的 k 個愁溜,這類問題我們稱為 TOPK 問題疾嗅,通常使用堆來解決:

  • 求前 k 大,用最小堆
  • 求前 k 小冕象,用最大堆

例子

現(xiàn)有列表 [1, 2, 0, 3, 5], 求前 2 個大的元素代承。

如傳入列表和 k = 2,輸出 [3, 5]渐扮。

思路

  1. 先放入元素前 k 個建立一個最小堆

  2. 迭代剩余元素:

    如果當(dāng)前元素小于堆頂元素论悴,跳過該元素(肯定不是前 k 大)

    否則替換堆頂元素為當(dāng)前元素,并重新調(diào)整堆

  3. 最后獲取 最小堆 中的值墓律,即為 topk

image.png

代碼如下

import heapq

class Topk:
    """獲取大量元素 topk 大個元素膀估,固定內(nèi)存
    思路:
    1. 先放入元素前 k 個建立一個最小堆
    2. 迭代剩余元素:
        如果當(dāng)前元素小于堆頂元素,跳過該元素(肯定不是前 k 大)
        否則替換堆頂元素為當(dāng)前元素只锻,并重新調(diào)整堆
    """
    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k
        self.iterable = iterable

    def push(self, val):
        if len(self.minheap) >= self.capacity:
            min_val = self.minheap[0]
            if val < min_val:       # 當(dāng)然你可以直接 if val > min_val 操作玖像,這里我只是顯示指出跳過這個元素
                pass
            else:
                heapq.heapreplace(self.minheap, val)    # 返回并且 pop 堆頂最小值,推出新的 val 值并調(diào)整堆
        else:
            heapq.heappush(self.minheap, val)           # 前面 k 個元素直接放入 minheap

    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap

def test():
    import random
    i = list(range(1000))   # 這里可以是一個可迭代元素齐饮,節(jié)省內(nèi)存
    random.shuffle(i)
    _ = Topk(i, 10)
    print(_.get_topk())     # [990, 992, 991, 993, 996, 997, 998, 994, 995, 999]

test()
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末捐寥,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子祖驱,更是在濱河造成了極大的恐慌握恳,老刑警劉巖,帶你破解...
    沈念sama閱讀 206,311評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件捺僻,死亡現(xiàn)場離奇詭異乡洼,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)匕坯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,339評論 2 382
  • 文/潘曉璐 我一進(jìn)店門束昵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人葛峻,你說我怎么就攤上這事锹雏。” “怎么了术奖?”我有些...
    開封第一講書人閱讀 152,671評論 0 342
  • 文/不壞的土叔 我叫張陵礁遵,是天一觀的道長。 經(jīng)常有香客問我采记,道長佣耐,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 55,252評論 1 279
  • 正文 為了忘掉前任唧龄,我火速辦了婚禮兼砖,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘。我一直安慰自己掖鱼,他們只是感情好然走,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,253評論 5 371
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著戏挡,像睡著了一般。 火紅的嫁衣襯著肌膚如雪晨仑。 梳的紋絲不亂的頭發(fā)上褐墅,一...
    開封第一講書人閱讀 49,031評論 1 285
  • 那天,我揣著相機(jī)與錄音洪己,去河邊找鬼妥凳。 笑死,一個胖子當(dāng)著我的面吹牛答捕,可吹牛的內(nèi)容都是我干的逝钥。 我是一名探鬼主播,決...
    沈念sama閱讀 38,340評論 3 399
  • 文/蒼蘭香墨 我猛地睜開眼拱镐,長吁一口氣:“原來是場噩夢啊……” “哼艘款!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起沃琅,我...
    開封第一講書人閱讀 36,973評論 0 259
  • 序言:老撾萬榮一對情侶失蹤哗咆,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后益眉,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體晌柬,經(jīng)...
    沈念sama閱讀 43,466評論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,937評論 2 323
  • 正文 我和宋清朗相戀三年郭脂,在試婚紗的時候發(fā)現(xiàn)自己被綠了年碘。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,039評論 1 333
  • 序言:一個原本活蹦亂跳的男人離奇死亡展鸡,死狀恐怖屿衅,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情娱颊,我是刑警寧澤傲诵,帶...
    沈念sama閱讀 33,701評論 4 323
  • 正文 年R本政府宣布,位于F島的核電站箱硕,受9級特大地震影響拴竹,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜剧罩,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,254評論 3 307
  • 文/蒙蒙 一栓拜、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧,春花似錦幕与、人聲如沸挑势。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,259評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽潮饱。三九已至,卻和暖如春诫给,著一層夾襖步出監(jiān)牢的瞬間香拉,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,485評論 1 262
  • 我被黑心中介騙來泰國打工中狂, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留凫碌,地道東北人。 一個月前我還...
    沈念sama閱讀 45,497評論 2 354
  • 正文 我出身青樓胃榕,卻偏偏與公主長得像盛险,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子勋又,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,786評論 2 345

推薦閱讀更多精彩內(nèi)容

  • 堆的定義 堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)赐写,可以形象化的看成一顆完全二叉樹鸟蜡,一般內(nèi)部的存儲結(jié)構(gòu)為數(shù)組;堆中的某個節(jié)點(diǎn)總是不大...
    yandaren閱讀 2,773評論 0 5
  • 我的博客地址:https://rebornc.github.io/2018/11/15/%E5%A0%86%E6%...
    白夜叉小分隊(duì)閱讀 1,960評論 0 5
  • 面試中常會被問到的一個經(jīng)典問題就是給定一個無序的數(shù)(N個)挺邀,尋找其中最大(最腥嗤) 的K個(K<N)。 思路一:對整...
    小蛋子閱讀 807評論 0 1
  • 如下圖端铛,將一個數(shù)組轉(zhuǎn)化堆泣矛,有如下性質(zhì) 所有父節(jié)點(diǎn)的值小于或等于兩個子節(jié)點(diǎn)的值(最小堆) 如果有左子樹,那么左子樹的...
    Acamy丶閱讀 2,509評論 0 3
  • 拔牙后的第三天禾蚕,我終于沒有那么明確的感覺到疼痛您朽,雖然還是有些臉腫和張不開嘴。我忽然發(fā)現(xiàn)我身邊有個可愛的女子换淆,有那么...
    luory閱讀 180評論 4 0