heap_堆_PriorityQueues

一、概念

1.  Priority Queues：即带有优先级的队列（先进先出），较好实现方式：大根堆，或小根堆。

2.  堆总是满足下列性质：

a.  堆中某个节点的值总是不大于或不小于其父节点的值；

b.  堆总是一棵完全二叉树。

将根节点最大的堆叫做大根堆，根节点最小的堆叫做小根堆（binary min-heap （minimum key is at the root））。

3.  满二叉树与完全二叉树：

如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

二、堆 -> 数组

“堆”存储在数组中，某个 i（数组下标）节点的孩子的数组下标为：i * 2，i * 2 + 1，例如：

X   T O   G S M N    A E R A I B

1   2 3     4 5 6 7     8 9 10 11 12    (数组下标从1开始，也可以从0开始)

三、downheap() 与 upheap()

1.  downheap() -> O(log n)

删除 root -> 堆的最后一个节点替换 root -> "修复堆"，root如果有必要与"子节点"交换 -> 被改变的子节点继续"修复堆"

2. upheap()-> O(log n)

插入一个节点到堆的最后 ->  "修复堆"，该节点如果有必要与"父节点"交换 -> 被改变的父节点继续 "修复堆"

四、堆 -> 构造

1. downheap() -> O(n)

bottom-up heap construction 自下而上堆的构造

自下而上，从右至左的方向，找到第一个“非叶子节点”，如果有必要与"子节点"交换（如果左右节点相等，交换任意一个都可）

即用 downleap() 方法，对每一个子堆

2. upheap() -> O(n log n)

一个一个节点增加到堆的最后 -> 用 upheap() 方法"修复堆"

五、堆排序

堆排序：O(n log n)