5 堆和优先队列

定义

优先队列：priority queue 取出元素的顺序是依据元素的优先权大小，而不是元素进入队列的先后顺序
两个操作：插入和删除

实现方法

1. 数组：
   插入：O(1)
   删除：
   1）查找最大或最小O(n)
   2) 删除需要移动元素O(n)

2. 队列：
   插入：O(1)
   删除：
   1）查找最大或最小O(n)
   2）删除O(1)

3. 有序数组
   插入：
   1）找到要插入的位置 O(n)
   2) 移动元素并插入 O(n)
   删除：O(1)

4. 有序列表
   插入 ：
   1）找到合适位置 O(n)
   2) 插入元素O(1)
   删除：O(1)

最优方法 — 堆

特性

1. 结构性：用数组表示的完全二叉树
2. 有序性：任一节点的关键字是其子树所有节点的最大值(最小值)
   最大堆（MaxHeap）
   最小堆（MinHeap）
3. 堆的抽象数据描述
   类型名称：最大堆
   数据对象集：完全二叉树，每个结点的元素值不小于其子节点的元素值
   操作集：
   MaxHeap Create( int MaxSize ): 创建一个空的最大堆
   Boolean isFull(MaxHeap H): 判断最大堆H是否已满
   Insert( MaxHeap H, ElementType item ): 将元素item插入最大堆H
   Boolean isEmpty(MaxHeap H): 判断是否为空
   ElementType DeleteMax(MaxHeap H): 删除最大元素，并返回该元素值