zh-hant/chapter_heap/top_k/

[giscus[bot]]

zh-hant/chapter_heap/top_k/

動畫圖解、一鍵執行的資料結構與演算法教程

https://www.hello-algo.com/zh-hant/chapter_heap/top_k/

[boyonglin]

方法三應該是初始化一個大頂堆積嗎？

[kyomind]

是初始化「小頂堆積」沒錯。使用小頂堆積的原因在於它可以高效地保留一組數值中「最大的 K 個元素」

小頂堆積的頂部始終是堆積中最小的元素，因此在接下來從第 K+1 個元素開始比較時，我們只需要跟堆積頂（當前已知最小值）進行比較：

• 如果新元素比堆積頂更大，表示它有可能屬於最大的 K 個元素，因此我們將堆積頂移出並插入新元素
• 如果新元素小於或等於堆積頂，則略過，因為它已經不可能進入最大的 K 個範圍

如此反覆，最後小頂堆積中留下的元素就是陣列中最大的 K 個值，因為我們持續地淘汰了不夠大的元素