[資料結構] Binary Heap

TL;DR;

• Binary Heap 和記憶體中的 Heap 沒有關係
• Parent 的數值一定大於 Child

Binary Heap

圖片來源：https://en.wikipedia.org/wiki/Heap_(data_structure)#/media/File:Max-Heap.svg

• Binary Heap 中 parent node 的數值，一定大於 child node 的數值。
• root 會是所有 Node 中的最大值。
• Binary Heap 很常被使用在 Priority Queue。

信息

Priority Queue 和一般的 Queue 不同，一般的 Queue 一定是先進先出，但 Priority Queue 中排隊的人是有權重關係的，優先順序越高的人可以超車。以實際的例子來說，就像迪士尼出的快速通關證一樣，玩遊樂設施時一般人都在排隊，但有快速通行證的人可以排另一條更快進場的通道。

Time Complexity

由於 Binary Heap 並不像 Binary Search Tree 本身就保留順序關係在內，因此其 lookup 的 Big O 會是 O(n)。

• Lookup: O(n)
• Insert: O(log N)
• Delete: O(log N)