优先队列

优先队列是堆的常见应用，优先队列也有两种形式:最大优先队列和最小优先队列
优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字，其中最大优先队列的典型应用就是共享计算机系统的作业调度。
一个最大优先队列支持以下四个操作：

• INSERT(S, x)，把元素x插入集合S中
• MAXIMUM(S)，返回S中具有最大键字的元素
• EXTRACT-MAX(S)，去掉并返回S中的具有最大键字的元素
• INCREASE-KEY(S, x, k)，将元素x的关键字值增加到k

MAXIMUM(S)

可通过HEAP-MAXIMUM在O(1)时间内实现MAXIMUM操作

HEAP-MAXIMUM(A)
  return A[1]

EXTRACT-MAX(S)

可通过HEAP-EXTARCT-MAX实现，类似于堆排序中HEADPSORT过程中的for循环体

HEAP-EXTRACT-MAX(A)
  if A.heap-size < 1
    error "heap underflow"
  max = A[1]
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size - 1
  MAX-HEAPIFY(A, 1)
  return max

INCREASE-KEY(S, x, k)

HEAP-INCREASE-KEY(A, i, key)
  if key < A[I]
    error "new key is smaller than current key"
  A[I] = key
  while i > 1 and A[PARENT(i)] < A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)

INSERT(S, x)

MAX-HEAP-INSERT(A, key)
  A.heap-size = A.heap-size + 1
  A[A.heap-size] = math.MinInt32
  HEAP-INCREASE-KEY(A, A.heap-size, key)