Q：Top K問題：從海量數(shù)據(jù)n中找出前K個數(shù)據(jù)？

• 使用 排序算法 進行全排序，時間復雜度
• 使用 數(shù)據(jù)結(jié)構(gòu) 二叉堆 來解決，時間復雜度
  1.使用小頂堆
  2.將前個數(shù)放入堆中，然后從個數(shù)開始，如果大于堆頂元素，replace操作
  3.掃描完畢后，堆中剩下的就是最大的前個數(shù)

1. 二叉堆（Heap）

(1) 定義

堆（Heap）：是一種樹狀的數(shù)據(jù)結(jié)構(gòu)

• 堆中的元素必須具備 可比較性
• 任意節(jié)點的值總是 或 子節(jié)點的值
  如果任意節(jié)點的值總是 子節(jié)點 的值，稱為：最大堆、大根堆、大頂堆
  如果任意節(jié)點的值總是 子節(jié)點 的值，稱為：最小堆、小根堆、小頂堆

最大堆_二叉堆、最小堆_二叉堆

2. 二叉堆（Binary Heap）

(1) 定義

二叉堆（Binary Heap）：邏輯結(jié)構(gòu)就是一棵完全二叉樹，也叫完全二叉堆
二叉堆的底層一般用數(shù)組實現(xiàn)即可

二叉堆

索引 i 的規(guī)律（n是元素數(shù)量）

• 如果，它是根節(jié)點
• 如果，它的父節(jié)點的索引為
• 如果，它的左子節(jié)點的索引為
• 如果，它沒有左子節(jié)點
• 如果，它的右子節(jié)點的索引為
• 如果，它沒有右子節(jié)點

(2) 最大堆 - 添加

上濾（Sift Up）：時間復雜度

• 循環(huán)執(zhí)行以下操作
  如果 node 父節(jié)點 - 與父節(jié)點交換位置
  如果 node 父節(jié)點，或者node沒有父節(jié)點 - 退出循環(huán)

上濾

(3) 最大堆 - 刪除

下濾（Sift Down）：時間復雜度

• 用最后一個節(jié)點 覆蓋 根節(jié)點
• 刪除 最后一個節(jié)點
• 循環(huán)執(zhí)行以下操作
  如果 node 最大子節(jié)點 - 與最大子節(jié)點交換位置
  如果 node 最大子節(jié)點，或者node沒有子節(jié)點 - 退出循環(huán)

下濾

(4) 最大堆 - 批量建堆（Heapify）

批量建堆2種方法：

• 自上而下的上濾
• 自下而上的下濾

1> 自上而下的上濾

自上而下的上濾 本質(zhì)是：添加

自上而下的上濾

2> 自下而上的下濾

自上而下的上濾 本質(zhì)是：刪除

自下而上的下濾

3> 效率對比

所有節(jié)點的深度之和

• 僅僅是葉子節(jié)點，就有近 個每個葉子節(jié)點的深度是 級別

所有節(jié)點的高度之和

• 假設(shè)是滿樹，節(jié)點總個數(shù)為，樹高為，那么
• 所有節(jié)點的樹高之和

效率對比