Skip to main content

[資料結構] Binary Heap

TL;DR;#

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

Binary Heap#

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
info

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)
Last updated on