堆

思考：多个任务需要执行，如何调整其执行顺序？
优先队列：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

若采用数组或者链表实现优先队列：
数组：插入－元素总是插入尾部；删除－查找最大（或最小）关键字 从数组中删去需要移动元素
链表：插入－元素总是插入链表的头部；删除－查找最大（或最小）关键字 删去结点
有序数组：插入－找到合适位置 移动元素并插入；删除－删去最后一个元素
有序链表：插入－找到合适位置 插入元素；删除－删去最后一个元素或首元素

是否可以采用二叉树存储结构？
二叉搜索树？不能简单地利用二叉搜索树，输入插入、删除操作都比较简单，但当我们每次都删除最大值（即最右结点）会导致搜索树变斜，高度不变 复杂度也不变
如果采用二叉树结构，应该更加关注删除；树结点顺序安排：根结点为最大值 每次删除都删除根结点，树的结构采用完全二叉树 任何结点值都比左右子树结点值大。

－堆的两个特性：

结构性：用数组表示的完全二叉树
有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）
“最大堆（MaxHeap）”也称“大顶堆”：最大值；“最小堆（MinHeap）”也称“小顶堆”：最小值

－最大堆的主要操作：

－最大堆的创建：

typedef struct HeapStruct *MaxHeap ;
struct HeapStruct {
ElementType *Element ; // 存储堆元素的数组
int Size; // 堆的当前元素个数
int Capacity ; // 堆的最大容量
}

MaxHeap Create ( int MaxSize )
{ // 创建容量为MaxSize的空的最大堆
MaxHeap H = malloc ( sizeof ( struct HeapStruct ) ) ;
H -> Elements = malloc ( ( MaxSize + 1 ) * sizeof ( ElementType ) ) ;
// 下标为1的位置开始存值，下标为0的位置不存放堆元素
H -> Size = 0 ;
H -> Capacity = MaxSize ;
H -> Element [0] = MaxData ; // 定义“哨兵”为大于堆中所有可能元素的值 便于以后更快操作
return H ;
}

－最大堆的插入：

void Insert ( MaxHeap H , ElementType item )
{ // 将元素item插入最大堆H，其中H -> Elements [0] 已经定义为哨兵
int i ;
if ( IsFull ( H ) ) {
printf ( “最大堆已满” ) ;
return ;
}
i = ++H -> Size ; // i 指向插入后堆中的最后一个元素的位置
for ( ; H -> Elements [ i/2 ] < item; i /= 2 ) // 与父结点做比较，i / 2 表示的就是父结点的下标
H -> Element [ i ] = H -> Elements [ i/2 ]; // 向下过滤结点
H -> Elements [ i ] = item ; // 将 item 插入
}
H -> Element [ 0 ]是哨兵元素，它不小于堆中的最大元素 控制循环结束（哨兵比所有值都大 所以当插入的新元素比较大要放入下标为1位置时就直接与哨兵比较 循环结束新元素插入树的最顶层；若没有哨兵 则需要对 i 判断 当 i == 1时就可知道插入的新元素是最大值）

－最大堆的删除：

取出根结点（最大值）元素，同时删除堆的一个结点
步骤：1.将根结点删除，2.把位置最后那个结点移至根结点位置 即下标为1的位置，3.找出此时根结点中较大的孩子 并使其与根结点交换位置 重复该步骤直到最后
ElementType DeleteMax ( MaxHeap H )
{ // 从最大堆H中取出键值为最大的元素 并删除一个结点
int Parent, Child ;
ElementType MaxItem , temp ;
if ( IsEmpty ( H ) ) {
printf ( “最大堆以为空” ) ;
return;
}
MaxItem = H -> Elements [ 1 ] ; // 取出根结点最大值
// 用最大堆中最后一个元素从根结点开始向上过滤下层结点
temp = H -> Elements [ H -> Size — ] ;
for ( Parent = 1; Parent * 2 <= H -> Size ; Parent = Child ){
Child = Parent * 2 ;
if ( ( Child != H -> Size ) && ( H -> Elements [Child] < H -> Elements [Child + 1] ) )
Child ++; // Child指向左右结点的较大者
if ( temp >= H -> Elements [ Child ] ) break ;
else // 移动temp元素到下一层
H -> Elements [ Parent ] = H -> Elements [ Child ] ;
}
H -> Elements [ Parent ] = temp ;
return MaxItem ;
}

－最大堆的建立：

堆的一个应用是：堆排序，需要先建堆
建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O( N logN )。
方法2：在线性时间复杂度下建立最大堆。
（1）将N个元素按输入顺序存入，先满足完全二叉树的结构特性
（2）调整各结点位置，以满足最大堆的有序特性
倒数第一个有儿子的结点开始 逐渐将它们调整成堆（调整：将结点与其左右儿子中比较大的儿子交换位置 直到结点比它左右儿子都大为止）