iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 17

【Day17】[資料結構]-堆積Heap

堆積(Heap)是一種特別的完全二元樹,又分為最小堆積(Min-Heap)最大堆積(Max-Heap)

最小堆積(Min-Heap)

  • 樹根(Root)會是所有節點最小值
  • 所有的父節點的值都比子節點小。

https://ithelp.ithome.com.tw/upload/images/20210928/201210274K4qeSzXeV.jpg

最大堆積(Max-Heap)

  • 樹根(Root)會是所有節點最大值
  • 所有的父節點的值都比子節點大。

https://ithelp.ithome.com.tw/upload/images/20210928/20121027ZIiLFCOt0X.jpg


製作堆積(最大堆積為例)

https://ithelp.ithome.com.tw/upload/images/20210928/20121027YHNMhucWpH.jpg


新增節點至堆積(最大堆積為例)

插入7至空節點,7比父節點5大,兩者交換。
https://ithelp.ithome.com.tw/upload/images/20210928/201210274904xtgrMf.jpg


刪除節點(最大堆積為例)

預刪除節點4與最後節點5交換後再移除4,接著5跟其他節點作堆積比較。
https://ithelp.ithome.com.tw/upload/images/20210928/20121027H4ARKzGEmG.jpg

堆積可用來製作優先佇列,每個元素有不同優先權,若要取出最大權的元素,可用最大堆積,反之,則用最小堆積。佇列的介紹可以參考此篇


上一篇
【Day16】[資料結構]-二元搜尋樹Binary Search Tree-實作
下一篇
【Day18】[資料結構]-堆積Heap-實作
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言