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