## 堆 * `堆结构`就是用`数组`实现的`完全二叉树`结构 * 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆。 * 完全二叉树中如果每棵字数的最小值都在顶部就是小根堆。 * 堆结构有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)