二叉堆（英語：binary heap）是一種特殊的堆，二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足堆特性：父節點的鍵值總是保持固定的序關系于任何一個子節點的鍵值，且每個節點的左子樹和右子樹都是一個二叉堆。

當父節點的鍵值總是大于或等于任何一個子節點的鍵值時為“最大堆”。當父節點的鍵值總是小于或等于任何一個子節點的鍵值時為“最小堆”。

None Some(90) [90, 87, 61, 69, 31, 9, 23, 11]------------------ (program exited with code: 0)請按任意鍵繼續. . . use std::collections::BinaryHeap; fn main() {let mut my_heap=BinaryHeap::new();println!("{:?}",my_heap.peek());let x=[11,31,9,87,90,61,23,69];for i in &x{my_heap.push(i);}println!("{:?}",my_heap.peek());println!("{:?}",my_heap); }

二叉堆一般用數組來表示。如果根節點在數組中的位置是1，第n個位置的子節點分別在2n和 2n+1。因此，第1個位置的子節點在2和3，第2個位置的子節點在4和5。以此類推。這種基于1的數組存儲方式便于尋找父節點和子節點。

如果存儲數組的下標基于0，那么下標為i的節點的子節點是2i + 1與2i + 2；其父節點的下標是?floor((i ? 1) ∕ 2)?。函數floor(x)的功能是“向下取整”，或者說“向下舍入”，即取不大于x的最大整數（與“四舍五入”不同，向下取整是直接取按照數軸上最接近要求值的左邊值，即不大于要求值的最大的那個值）。比如floor(1.1)、floor(1.9)都返回1。

如下圖的兩個堆：

1 11 / \ / \ 2 3 9 10/ \ / \ / \ / \ 4 5 6 7 5 6 7 8/ \ / \ / \ / \8 9 10 11 1 2 3 4

將這兩個堆保存在以1開始的數組中：

位置: 1 2 3 4 5 6 7 8 9 10 11
左圖: 1 2 3 4 5 6 7 8 9 10 11
右圖: 11 9 10 5 6 7 8 1 2 3 4
對于一個很大的堆，這種存儲是低效的。因為節點的子節點很可能在另外一個內存頁中。B-heap是一種效率更高的存儲方式，把每個子樹放到同一內存頁。

如果用指針鏈表存儲堆，那么需要能訪問葉節點的方法?？梢詫Χ鏄洹按┚€”(threading)方式，來依序遍歷這些節點。

總結

以上是生活随笔為你收集整理的rust(52)-二叉最大堆BinaryHeap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。