堆積(Heap)

第 11 屆 iThome 鐵人賽

DAY 21

自我挑戰組

透過JavaScript學習演算法與資料結構系列第 21 篇

11th鐵人賽

2019-09-22 22:54:18

2186 瀏覽

Heap是一種資料結構，使用一維陣列來儲存資料，可以把它想成Tree的概念。
Heap分成兩種，最小堆積(Min-Heap)、最大堆積(Max-Heap)。

Min-Heap

父節點的值小於子節點。
樹根(root)一定最所有節點的最小值。

Max-Heap

父節點的值大於子節點。
樹根(root)一定最所有節點的最大值。

Insert:
先把值放在最後的節點，值再逐一與其父節點比大小，若是Min-Heap則較大值當作子節點較小的值當父節點，逐一比較到Root節點；反之，Max-Heap則較小值當作子節點較大的值當父節點，逐一比較到Root節點。
Delete:
刪除一個節點的值，就要將原先的最後一個節點的值，移動到要刪除的節點，然後該節點需要依據Heap的規則與父節點、子節點比較值的大小，完成一個新的Heap Tree。