概念
优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
问题：如何组织优先队列？
- 一般的数组、链表？
- 有序的数组或者链表？
- 二叉搜索树？ AVL树？
堆的两个特性
- 结构性：用数组表示的完全二叉树；
- 有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)
- “最大堆(MaxHeap)”,也称“大顶堆”：最大值
- “最小堆(MinHeap)”,也称“小顶堆” ：最小值
堆的抽象数据类型描述
类型名称：最大堆（MaxHeap）
数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值
操作集：最大堆H ∈ MaxHeap，元素item ∈ ElementType，主要操作有：
- MaxHeap Create( int MaxSize )：创建一个空的最大堆。
- Boolean IsFull( MaxHeap H )：判断最大堆H是否已满。
- Insert( MaxHeap H, ElementType item )：将元素item插入最大堆H。
- Boolean IsEmpty( MaxHeap H )：判断最大堆H是否为空。
- ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高优先级)。
Java 关联
java.util.PriorityQueue