优先队列--Java

优先队列的java实现

注：当时写好之后忘了检查，这个优先队列有点缺陷～～～嘻嘻，不过我在工作环境中已经作了修改

package test;

import java.util.Comparator;

/**
 * @作用：优先队列
 * @author henry
 * @date 2010-4-30
 */
public class PriQueue<E> {

	private static int DEFAULT_CAPECITY = 11;
	private Object[] objs;
	private Comparator<? super E> comparator;
	private int size = 0;

	public PriQueue() {
		this(DEFAULT_CAPECITY, null);
	}

	public PriQueue(Comparator<? super E> comparator) {
		objs = new Object[DEFAULT_CAPECITY];
		this.comparator = comparator;
	}

	public PriQueue(int capecity, Comparator<? super E> comparator) {
		if (capecity < 0) {
			throw new IllegalArgumentException();
		}
		objs = new Object[++capecity];
		this.comparator = comparator;

		heapfix();
	}

	public PriQueue(int capecity) {
		this(capecity, null);
	}

	private void heapfix() {
		if (objs != null) {
			return;
		}

		for (int i = size >> 1; i > 0; i--) {
			fixdown(i);
		}
	}

	/**
	 * 插入数据
	 * @param o
	 */
	public void add(E o) {
		if (o == null) {
			throw new NullPointerException("你插入了一个空对象");
		}

		if (size > Integer.MAX_VALUE) {
			throw new OutOfMemoryError("数组爆了，不能再插入！");
		}

		if (++size >= objs.length) {
			grow(size);
		}

		objs[size] = o;
		fixup(size);

	}

	/**
	 * 交换数据
	 * @param i
	 * @param k
	 */
	private void exchange(int i, int k) {

		if (i < 1 || k < 1 || i > Integer.MAX_VALUE || k > Integer.MAX_VALUE) {
			throw new IllegalArgumentException();
		}

		Object tmp = objs[i];
		objs[i] = objs[k];
		objs[k] = tmp;
	}

	/**
	 * 比较节点数据
	 * @param o1
	 * @param o2
	 * @return int
	 */
	@SuppressWarnings("unchecked")
	public int compare(E o1, E o2) {
		if (this.comparator != null) {
			return this.comparator.compare(o1, o2);
		} else {
			return ((Comparable<E>) o1).compareTo(o2);
		}
	}

	/**
	 * 增长队列
	 * @param index
	 */
	public void grow(int index) {
		if (index > Integer.MAX_VALUE) {
			throw new IllegalArgumentException("插入太多了～～");
		}

		int newLen = objs.length;
		if (index < newLen) {
			return;
		}

		if (newLen < index) {
			if (newLen < Integer.MAX_VALUE >> 1) {
				newLen = Integer.MAX_VALUE;
			} else {
				newLen <<= 1;//如果index > newLen，至少超出数组界限两位
			}
		}

		Object[] tmp = new Object[newLen + 1];
		System.arraycopy(objs, 0, tmp, 0, objs.length);

		objs = tmp;
	}

	/**
	 * 最大堆排序
	 * @param index
	 */
	@SuppressWarnings("unchecked")
	private void fixup(int index) {
		if (index <= 1 || index > Integer.MAX_VALUE) {
			return;
		}

		int p = index >>> 1;
		if (compare((E) objs[p], (E) objs[index]) < 0) {
			exchange(p, index);
		}

		fixup(p);
	}

	/**
	 * 最小堆排序
	 * @param i
	 */
	@SuppressWarnings("unchecked")
	private void fixdown(int i) {

		if (i >= size) {
			return;
		}

		int largest = i;
		int left = i << 1;
		int right = left + 1;

		if (left > size) {
			return;
		}

		if (right > size) {
			right = left;
		}

		if (compare((E) objs[largest], (E) objs[left]) < 0) {
			largest = left;
		}

		if (compare((E) objs[largest], (E) objs[right]) < 0) {
			largest = right;
		}

		if (i != largest) {
			exchange(i, largest);
			fixdown(largest);
		}

	}

	/**
	 * 检查队列是否还有数据
	 * @return boolean
	 */
	public boolean isHasElement() {
		if (size > 0) {
			return true;
		}

		return false;
	}

	/**
	 * 获取数据，但不会移除数据
	 * @param index
	 * @return Object
	 */
	public Object get(int index) {
		if (index > size || index < 0) {
			throw new IllegalArgumentException();
		}

		return objs[index + 1];
	}

	/**
	 * 获取数据，并移除队列的头部
	 * @return
	 */
	public Object poll() {
		if (objs.length > 1)
			return remove(1);

		return null;
	}

	/**
	 * 获取指定位置的数据，并移除
	 * @param i
	 * @return
	 */
	public Object remove(int i) {

		if (i > Integer.MAX_VALUE) {
			throw new OutOfMemoryError("索引值过大");
		}

		if(i > size) {
			throw new OutOfMemoryError("超出队列范围");
		}
		
		if (i < 1) {
			return null;
		}

		exchange(i, size);
		--size;
		fixdown(i);
		return objs[size + 1];
	}

	/**
	 * 移除指定元素，并取之
	 * 不存在该元素，则返回null
	 * @param o
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public Object remove(E o) {
		for(int i = 0; i < objs.length; i++) {
			if(this.compare(o, (E)objs[i]) == 0) {
				return remove(i);
			}
		}
		
		return null;
	}
	
	public static void main(String[] args) {

		int[] arr = { 1, 5, 2, 33, 20, 11, 8 };
		PriQueue<Integer> q = new PriQueue<Integer>(5);

		for (int a : arr) {
			q.add(a);
		}

		System.out.println("最大堆：");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(q.get(i) + " ");
		}
		System.out.println();

		System.out.println("最小堆：");
		StringBuilder sb = new StringBuilder();
		while (q.isHasElement()) {
			sb.append(q.poll() + " ");
		}

		System.out.println(sb.toString());
	}
}