java优先级列表（Java中优先队列的理解和使用）
java优先级列表（Java中优先队列的理解和使用）//查看元素是否存在的本质就是看看有没有他的位置 public boolean contains(Object o) { return indexOf(o) != -1; }toArray()//先找出位置，再进行删除 public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } }contains()//调用了offer方法 public boolean add(E e) { return offer(e); } //判断输入元素是否为空，如果不为空 public boolean offer(E e) { if (e == null) throw new Nul
1 什么是优先队列（堆）1.1 继承关系首先看下Java中堆的继承关系，可以看出堆实现了队列的全部方法。
（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 " ");
}
}
}
运行结果：
堆在操作系统的进程调度中也被广泛使用，比如依据优先级进行的进程调度等等，在这里就不做详解啦
