談談堆積(Heap)吧！

今天來談談堆積(Heap)吧！堆積是一種特別的二元樹(Binary tree)，那什麼又是二元樹？讓我們一個一個來解析。

二元樹（Binary tree)

樹是由節點組成的資料結構

在電腦科學中，二元樹只有不超過兩個節點(左節點或右節點)的分支，常用於搜尋演算法中。
下圖中可以看到，最上面的A為Root，也就是根節點，也可被稱為父節點。對於B、C來說，A就是他們的父親節點，用家族族譜的方式來理解二元樹會更容易上手。

注意：左、右節點是有次序之分。

二元樹分類

常見的二元樹分類有兩種，第一種是完整二元樹、第二種是完美二元樹，下列會用列點的方式來整理兩者的差異：

1. Complete Tree
   • 最後一層的節點為基數

2. Full Tree
   • 最後一層的節點為偶數
   • 必須為k^2-1個節點

堆積(Heap)

談完了二元樹，現在回到正題，什麼是堆積，讓我們來看看下圖，會比較清楚：

從上圖中可以看到，二元樹的構造以及對應放入的array中，順序依次由上到下，再從左到右。

分享一篇寫得很清楚的堆積排序法(Heap Sort)，今天就先不分享程式碼，提供其他人的文章給大家參考摟！

http://seanleetech.com/algorithm/168/

延伸閱讀：

Python官方文件-堆積佇列 (heap queue) 演算法

https://docs.python.org/zh-tw/3.8/library/heapq.html