Day 16：堆积(heap)与字首树(trie)

上一回写到树，今天的主题是以树结构为基础的资料结构。

堆积

二元树(binary tree)是每个节点最多只有两个子节点的树结构，而其中完全二元树(complete binary tree)是指除了最後一层有可能没有填满外，其余中间每一层的满节点的二元树，也就是一个节点都一定有两个子节点。最後一层如果是不满的情况，则节点都会在该层的左侧。

堆积就是一种特别的完全二元树，它的任一节点的值会比其子节点的值小(或大)。如果任一节点比子节点小，称为最小堆积(min heap, 如下图左)；任一节点比子节点大，则称为最大堆积(max heap, 如下图右)。

图片来源：GeeksforGeeks

堆积的结构让存取最大或最小元素只需要O(1)，可以应用来提升很多演算法的效率。其中一个很常与堆积一起提到的演算法就是堆积排序(heapsort)。

以由大到小的排序来说，堆积排序的作法是先将要排序的元素组成一个堆积，接着反覆将最大的节点移除，同时维持剩下的节点为堆积的结构，直到只剩一个节点，则排序结束。堆积排序可以说是选择排序的进化版，它也是逐一将最大的元素排序进阵列中，不过因为资料结构确保了最大元素的存取，就省去了每一轮比较所有元素的操作。最坏情况执行时间为O(n log n)。

字首树

trie(音'try')，又称作字首树(prefixed tree)，是一种搜寻树的资料结构，通常用来储存比较复杂的资料，如字串。它与二分搜寻树不同的地方在於，二分搜寻树会在一个节点上储存整个资料(一个字串)；字首树的一个节点上则只储存字串中着一个字元(character)。透过搜寻一个节点的所有子节点可以存取字串。

以下图来说，从根节点开始，可以透过相连的节点搜寻到geer这个字串，而第二个e以下任何子节点组成的字串也都会共用gee这个字首，例如geeks。

图片来源：GeeksforGeeks

实作上，字首树可以是以阵列作为节点的树，阵列均由字母组成。以储存的一个字串来说，字串的第一个字母会指向一个阵列，阵列中的下个字母会再指向一个阵列...直到最後一个字母以布林值表达字串结束。若搜寻时碰到一个阵列中没有下一个阵列的参照或布林值，则代表的找想的字不在树中。

在字首树中搜寻任一长度为m个字元的字串，只要经过m个步骤。而且m不会因为树中的总字串数(n)增加而改变，也就是可以实现O(1)的搜寻，相较之下比二分搜寻树的O(log n)还快。不过搜寻速度这麽快的同时，可以想像字首树的空间需求非常高。