Aloha～又是我少女人妻 Uerica！今天是教师节啊～大家小时候都会写感谢恩师的卡片吗？记得刚上国小的时候还有体罚，教师节时爸妈送了老师一面金牌写 "感谢恩师" ，然後拜托老师如果我不乖就用力打，呜呜呜到底为什麽啦～当时的我吓到乖得不得了呢 QQ...。

堆积 (heap)

堆积是图形结构中的树状结构中的一种，用於实践优先伫列 (Priority Queue) 。利用保持资料结构的一定规则 (从小到大或从大到小) ，来确保拿取资料的效率。

堆积的定义与特性

堆积一种特殊的二元树资料结构，但不全然相同，每个节点(node)最多只有两个子节点，而子节点与父节点之间要维持一定规则，同层的兄弟节点则无规则限制，但同一层要维持从左到右新增节点，满了才可增加下一层。

堆积的种类

• 最小堆积 Min heap : 父节点永远小於子节点
• 最大堆积 Max heap : 父节点永远大於子节点

常见的基本操作

插入 Insert

假设要插入一个资料元素到遵循最小堆积的结构中。

插入资料元素时，都先从最左下方开始。

插入元素後比对是否符合父节点永远小於子节点这个规则。

若不符合规则，则交换位置，直到符合为止。

删除 Delete

从最小的根节点删除或取出。

顺序最後一个子节点做替补。

若不符合父节点永远小於子节点这个规则则做交换，选择最小的子节点做交换。

再做比对，再交换。

直到符合规则为止。

堆积的时间复杂度

• 因根节点永远是最小或最大值，故取最小或最大值的时间复杂度为 O(1)
• 若取出元素需重整资料结构，时间复杂度为 O(log n)

参考资料

资料结构大便当： Binary Heap

堆积：维基百科

【资料结构和演算法】堆积, 堆积排序和优先伫列

Heap Tree

好啦～今天就先介绍到这里了，大家掰掰明天见啦！话说後来的老师都没收金牌，我就以为可以皮了，然後...然後就被打爆了 XD。