堆

优先队列（Priority Queue）

定义

特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序

如何组织优先队列

采用数组或者链表实现优先队列

数组 插入：元素总是插入尾部， Θ(1) 删除： 查找最大（或最小）关键字， Θ(n) 从数组中删去需要移动元素， O(n) 链表 插入：元素总是插入链表的头部， Θ(1) 删除： 查找最大（或最小）关键字， Θ(n) 删去结点， Θ(1) 有序数组 插入： 找到合适的位置， O(n)orO(logn2) 移动元素并插入， O(n) 删除：删去最后一个元素， Θ(1) 有序链表 插入： 找到合适的位置， O(n) 插入元素， Θ(1) 删除首元素或者最后元素， Θ(1)

采用完全二叉树表示

使用了完全二叉树去实现优先队列，这种完全二叉树还有一个名字——堆

堆的特性

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

最大堆的抽象数据类型描述

类型名称：最大堆（MaxHeap）数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值操作集：最大堆 H∈MaxHeap ，元素 item∈ElementType ，主要操作有： MaxHeap Create(int MaxSize)：创建一个空的最大堆Boolean IsFull(MaxHeap H)：判断最大堆H是否已满Insert(MaxHeap H, ElementType item)：将元素item插入最大堆HBoolean IsEmpty(MaxHeap H)：判断最大堆H是否为空ElementType DeleteMax(MaxHeap H)：返回H中最大元素（高优先级）

最大堆的操作

结构定义

typedef struct HeapStruct *MaxHeap; struct HeapStruct { ElementType *Elements; int Size; int Capacity; };

初始化（建立空的最大堆）

MaxHeap Create(int MaxSize) { MaxHeap H = malloc(sizeof(struct HeapStruct)); H->Elements = malloc((MaxSize + 1) * sizeof(ElementType)); H->Size = 0; H->Capacity = MaxSize; H->Elements[0] = MaxData; // 定义哨兵为大于堆中所有可能元素的值，便于以后更快操作 return H; }

插入操作

算法：将新增结点插入到从其父结点到根结点的有序序列中

// 将元素item插入最大堆H，其中H->Elements[0]已经定义为哨兵 void Insert(MaxHeap H, ElementType item) { int i; if (IsFull(MaxHeap)) { printf("最大堆已满"); return; } i = ++H->Size; // i指向插入后堆中的最后一个元素的位置 for (; H->Elements[i/2] < item; i /= 2) // H->Elements[0]是哨兵元素，它不小于堆中的最大元素，控制循环结束 H->Elements[i] = H->Elements[i/2]; // 向下过滤结点 H->Elements[i] = item; // 将item插入 }

时间复杂度： T(N)=O(logN)

删除操作

算法： 1. 将数组最末元素替代第一个元素（被删除的元素） 2. 与左右孩子结点进行比较 3. 如果存在这样的孩子结点，则将孩子结点上移，然后重复2，否则进入4 4. 结束循环后，将之前的最末元素赋给当前空出来的位置

// 从最大堆H取出键值为最大的元素并删除一个结点 ElementType DeleteMax(MaxHeap 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 H->Elements[Parent] = H->Elements[Child]; } H->Elements[Parent] = temp; return MaxItem; }

时间复杂度： T(N)=O(logN)

最大堆的建立

建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中 * 通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O(NlogN) * 在线性时间复杂度下建立最大堆（最坏情况下需要挪动元素次数是等于树中各结点的高度和）： 1. 将N个元素按输入顺序存入，先满足完全二叉树的结构特性 2. 调整各结点位置，以满足最大堆的有序特性，调整方式类似堆的删除： 1. 从倒数第一个有儿子结点的结点开始，将其看作堆，进行调整 2. 从下往上逐层进行调整，保证下层都是堆 3. 一直调整到根结点位置