## 堆 * `堆結構`就是用`數組`實現的`完全二叉樹`結構 * 完全二叉樹中如果每棵子樹的最大值都在頂部就是大根堆。 * 完全二叉樹中如果每棵字數的最小值都在頂部就是小根堆。 * 堆結構有2個重要操作，`heapInsert`和`heapify`。 * 優先級隊列就是堆實現的。 ## 數組實現堆 已知數組索引 `i` * 左節點的下標為 ` 2i + 1` * 右節點的下標為 `2i + 2` * 父節點的下標為 `(i-1)/2` ## heapInsert 向上調整 ~~~ /** * 加入元素到棧 * * @param t */ public void insert(T t) { this.data.add(t); int index = this.size; // 向上堆化 while (index>0 && this.compare(index,(index-1)/2)) { swap(index, (index - 1) / 2); index = (index - 1) / 2; } this.size++; } ~~~ ## heapfiy 向下調整 ~~~ /** * 向下堆化 * @param index 起始下標 * @param size 堆大小 */ public void heapfiy(int index, int size) { int left = index * 2 + 1; while (left < size) { int the = left + 1 < size && this.compare(left+1,left) ? left + 1 : left; the = this.compare(the,index) ? the : index; if (the == index) { break; } swap(the, index); index = the; left = index * 2 + 1; } } ~~~ ## 實現及應用 * [集合數組實現堆](../%E9%9B%86%E5%90%88%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0%E5%A0%86.md) * [Java系統堆優先隊列-堆排序](../Java%E7%B3%BB%E7%BB%9F%E5%A0%86%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md)