1 什么是优先队列（堆）

1.1 继承关系

首先看下Java中堆的继承关系，可以看出堆实现了队列的全部方法。

1.2 堆的数据结构

1.3 特征：

（1）二叉堆是一个完全二叉树

（2）根节点总是大于左右子节点（大顶堆），或者是小于左右子节点（小顶堆）。

1.4 常见方法

add()

//调用了offer方法
public boolean add(E e) {
  return offer(e);
}
//判断输入元素是否为空，如果不为空
public boolean offer(E e) {
  if (e == null)
    throw new NullPointerException();
  modCount++;
  int i = size;
  if (i >= queue.length)
    //增加容量
    grow(i + 1);
  size = i + 1;
  if (i == 0)
    queue[0] = e;
  else
    //上浮方法--（小根堆）将小的元素进行上浮
    siftUp(i, e);
  return true;
}

offer()

//判断输入元素是否为空，如果不为空
public boolean offer(E e) {
  if (e == null)
    throw new NullPointerException();
  modCount++;
  int i = size;
  if (i >= queue.length)
    //增加容量
    grow(i + 1);
  size = i + 1;
  if (i == 0)
    queue[0] = e;
  else
    //上浮方法--（小根堆）将小的元素进行上浮
    siftUp(i, e);
  return true;
}
//私有方法
/*
作用：在k位置插入项x，通过提升x到树的顶端，保持堆不变，直到它大于或等于它的父结点，
或者是根结点
*/
private void siftUp(int k, E x) {
  if (comparator != null)
    siftUpUsingComparator(k, x);
  else
    siftUpComparable(k, x);
}

peek()

//弹出堆顶的元素
public E peek() {
  return (size == 0) ? null : (E) queue[0];
}

remove()

//先找出位置，再进行删除
public boolean remove(Object o) {
  int i = indexOf(o);
  if (i == -1)
    return false;
  else {
    removeAt(i);
    return true;
  }
}

contains()

//查看元素是否存在的本质就是看看有没有他的位置
public boolean contains(Object o) {
  return indexOf(o) != -1;
}

toArray()

public Object[] toArray() {
  return Arrays.copyOf(queue, size);
}
//与上边的不同就是需要有一个泛型
public <T> T[] toArray(T[] a) {
  final int size = this.size;
  if (a.length < size)
    //返回一个新的带泛型的数组
    return (T[]) Arrays.copyOf(queue, size, a.getClass());
  System.arraycopy(queue, 0, a, 0, size);
  if (a.length > size)
    a[size] = null;
  return a;
}

size()

public int size() {
  return size;
}

clear()

//遍历一次 全部置为null
public void clear() {
  modCount++;
  for (int i = 0; i < size; i++)
    queue[i] = null;
  size = 0;
}

poll()

//返回并删除第一个元素
public E poll() {
  if (size == 0)
    return null;
  int s = --size;
  modCount++;
  //取出堆顶元素
  E result = (E) queue[0];
  //取出最后一个元素
  E x = (E) queue[s];
  queue[s] = null;
  if (s != 0)
    //做下沉操作
    siftDown(0, x);
  return result;
}

2 Java中堆的使用（小根堆为例）

2.1 堆排序

/**
* @author ymx
*/
public class TestPriorityQueue {
  /**
* 声明一个堆
*/
  public PriorityQueue<Integer> queue = new PriorityQueue();
/**
* 初始化数据
*
* @param items
*/
public void init(int[] items) {
  for (int i = 0; i < items.length; i++) {
    //将数据放入堆中
    queue.add(items[i]);
  }
}
/**
* 排序操作
*
* @return
*/
public int[] sort() {
  int[] items = new int[queue.size()];
  int i = 0;
  while (queue.size() > 0) {
    //弹出并删除堆顶元素
    items[i] = queue.poll();
    i++;
  }
  return items;
}
public static void main(String[] args) {
  TestPriorityQueue test = new TestPriorityQueue();
  test.init(new int[]{5, 6, 4, 3, 8, 9, 7, 1, 2});
int[] sort = test.sort();
System.out.print("排序结果：");
for (Integer i : sort) {
  System.out.print(i + " ");
}
}
}

运行结果：

2.2 进程调度

堆在操作系统的进程调度中也被广泛使用，比如依据优先级进行的进程调度等等，在这里就不做详解啦