老師ppt
What is Heap
Heap(Binary Heap) 是以 tree(樹) 為基礎的資料結構, 他有以下特點:
Shape Property: Heap 的資料結構永遠都是 完全二元樹 Complete Binary Tree, 也就是在每個 level(層級) ,由左至右都有 Node(節點),但是如果是同層級的左至右少一個結點,就不是完全二元樹了。(如下圖)
Heap Property: 所有節點再初始狀態下沒有大小排序. 但是當所有 parent nodes(父節點)> 所有的 child nodes(子節點), 就會稱作 Max-Heap。反之當所有 parent nodes(父節點)< 所有的 child nodes(子節點) Min-Heap。(如下圖)
它是 linked 的進化版,一般在 linked-List 裡的 Node 裡面,只會包含 value 和 pointer(往前或往後)。但是它把在 heap 裡面,它限制只能往一個方向