【Day17】[资料结构]-堆积Heap

堆积(Heap)是一种特别的完全二元树，又分为最小堆积(Min-Heap)、最大堆积(Max-Heap)。

最小堆积(Min-Heap)

• 树根(Root)会是所有节点最小值。
• 所有的父节点的值都比子节点小。

最大堆积(Max-Heap)

• 树根(Root)会是所有节点最大值。
• 所有的父节点的值都比子节点大。

制作堆积(最大堆积为例)

新增节点至堆积(最大堆积为例)

插入7至空节点，7比父节点5大，兩者交换。

删除节点(最大堆积为例)

预删除节点4与最後节点5交换後再移除4，接着5跟其他节点作堆积比较。

堆积可用来制作优先伫列，每个元素有不同优先权，若要取出最大权的元素，可用最大堆积，反之，则用最小堆积。伫列的介绍可以参考此篇