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

    堆的两个特性
    结构性：用数组表示的完全二叉树
    有序性：任一结点的关键字是其子树所有结点的最大值/最小值

    1. public class MaxHeap{
    3.     private int size; //当前元素个数
    4.     private int capacity; //容量
    5.     private int[] item;
    7.     MaxHeap(int capacity){
    8.         size = 0;
    9.         this.capacity = capacity;
    10.         item = new int[capacity + 1];
    11.         item[0] = Integer.MAX_VALUE; //哨兵
    12.     }
    14.     public void insert(int val){
    15.         if(isFull())
    16.             System.out.println("插入时最大堆已满");
    17.         else{
    18.             int i = size + 1; //指向末尾空的地方
    19.             while(val > item[i / 2]){
    20.                 item[i] = item[i / 2]; //把父节点换下来
    21.                 i = i / 2;
    22.             }
    23.             item[i] = val;
    24.             size ++;
    25.         }
    26.     }
    27.     public int delete(){
    28.         if(isEmpty()){
    29.             System.out.println("删除时最大堆为空");
    30.             return -1;
    31.         }
    32.         else{
    33.             int result = item[1]; //把最大值保存起来
    34.             int temp = item[size]; //取最后一个节点
    35.             size--;
    36.             int parent, child;
    37.             for(parent = 1; parent * 2 <= size; parent = child){
    38.                 child = parent * 2; //左儿子下标
    39.                 //右儿子存在且右儿子较大
    40.                 if(child != item.length && item[child] < item[child + 1]){
    41.                     child++; //指向右儿子
    42.                 }
    43.                 //此时child指向左右儿子中较大者
    44.                 if(temp > item[child])
    45.                     break;
    46.                 else //把大的换上来
    47.                     item[parent] = item[child];
    48.             }
    49.             item[parent] = temp;
    50.             return result;
    51.         }
    52.     }
    53.     public boolean isFull(){
    54.         return size == capacity;
    55.     }
    57.     public boolean isEmpty(){
    58.         return size == 0;
    59.     }
    61.     public static void main(String[] args) {
    62.         MaxHeap maxHeap = new MaxHeap(5);
    63.         maxHeap.insert(6);
    64.         maxHeap.insert(3);
    65.         maxHeap.insert(2);
    66.         maxHeap.insert(4);
    67.         maxHeap.insert(5);
    68.         System.out.println(maxHeap.delete());
    69.         System.out.println(maxHeap.delete());
    70.         System.out.println(maxHeap.delete());
    71.         System.out.println(maxHeap.delete());
    72.         System.out.println(maxHeap.delete());
    73.     }
    74. }

    因为堆是完全二叉树，一定是平衡的，插入、删除时间复杂度与树的高度有关：堆 - 图1

    建立堆时

    • 通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，时间代价为堆 - 图2
    • 将N个元素按输入顺序存入，先满足完全二叉树的结构特性。调整各结点位置，以满足最大堆的有序特性，时间代价为堆 - 图3