Java实现可泛型的Heap 博客分类： Accumulation heap算法堆排序

可泛型的Heap，方便使用。

Heap接口：

 

public interface Heap<T>
{
	/**
	 * return the top element of the heap
	 * 
	 * @return top element
	 */
	Object get();

	/**
	 * remove the top element of the heap and return it the heap must be fixed.
	 * 
	 * @return top element
	 */
	Object remove();

	/**
	 * reset the top element
	 * 
	 * @param obj
	 *            the new top element
	 */
	void set(T obj);

	/**
	 * add a element to the heap. if no comparator is set, the obj must be
	 * implments comparable interface
	 * 
	 * @param obj
	 *            the element to be added
	 */
	void add(T obj);

	/**
	 * if the heap is empty return true;
	 * 
	 * @return true if heap is empty,else false
	 */
	boolean isEmpty();

	/**
	 * clear the heap
	 */
	void clear();
}

 AbstractHeap类：

public class AbstractHeap<T> implements Heap<T>{

	private List<T> l = new ArrayList<T>(128);

	private Comparator<T> com;
	

	/*
     * 默认构造器
     * 接受泛型的数组
     */
	public AbstractHeap(T[] elements)
	{
		init(elements);
	}

	/*
     * 带Comparator的构造器
     * 如果com为null会抛出IllegalArgumentException
     */
	public AbstractHeap(Comparator<T> com, T[] elements)
	{
		if (com == null)
			throw new IllegalArgumentException("compartor can't be null");
		this.com = com;
		init(elements);
	}

	/*
     * 初始化Heap中的ArrayList
     */
	private void init(T[] elements)
	{
		l.add(null);
		for (int i = 0; i < elements.length; i++)
		{
			add(elements[i]);
		}
		System.out.println("Queue length is : " + l.size());
		System.out.println("Content is : " + l);
	}

	/*
     * 得到堆顶的元素
     */
	@Override
	public Object get()
	{
		return l.get(1);
	}

	/*
     * 移除堆顶端元素，并重新维护Heap
     */
	@Override
	public T remove()
	{
		T toReturn = l.get(1);
		T ret = l.get(l.size() - 1);
		l.set(1, ret);
		l.remove(l.size() - 1);
		
		fixDown(1);

		System.out.println("Queue length is : " + l.size());
		System.out.println("Content is : " + l);
		return toReturn;
	}
	/*
     * 检测Heap是否为空
     */
	@Override
	public boolean isEmpty()
	{
		return l.size() == 0;
	}

	/*
     * 情况Heap中所有元素
     */
	@Override
	public void clear()
	{
		l.clear();
	}

	/*
     * 将堆顶元素替换，并重新维护Heap
     */
	@Override
	public void set(T obj)
	{
		l.set(1, obj);
		fixDown(1);
	}

	/*
     * 向Heap中加入一个元素
     */
	@Override
	public void add(T obj)
	{
		l.add(obj);
		fixUP(l.size());
	}

	/*
     * 比较器
     */
	protected int compare(int i, int j) throws NoComparableException
	{
		if (com != null)
		{
			return com.compare(l.get(i), l.get(j));
		}
		else if (l.get(j) instanceof Comparable)
		{
			return ((Comparable) l.get(i)).compareTo(l.get(j));
		}
		else
		{
			throw new NoComparableException(
					"Not implements Comparable interface.");
		}
	}

	/*
     * 比较器
     */
	protected int compare(T i, T j) throws NoComparableException
	{
		if (com != null)
		{
			return com.compare(i, j);
		}
		else if (i instanceof Comparable)
		{
			return ((Comparable) i).compareTo(j);
		}
		else
		{
			throw new NoComparableException(
					"Not implements Comparable interface.");
		}
	}

	/*
     * 向上维护
     */
	private void fixUP(int start)
	{
		int k = start - 1;
		T s = l.get(k);
		try
		{
			while (k != 1 && compare(l.get(k >> 1), s) <= 0)
			{
				l.set(k, l.get(k >> 1));
				k >>= 1;

			}
		} catch (NoComparableException e)
		{
			e.printStackTrace();
		}
		l.set(k, s);
	}

	/*
     * 向下维护
     */
	private void fixDown(int k)
	{
		T ret = l.get(k);
		int j = k;
		int r = j * 2;
		int size = l.size() - 1;
		while (r <= size)
		{
			try
			{
				if (r < size && compare(l.get(r + 1), l.get(r)) > 0)
					r++;
				if (compare(l.get(r), ret) < 0)
					break;
			} catch (NoComparableException e)
			{
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			l.set(j, l.get(r));
			j = r;
			r *= 2;
		}
		l.set(j, ret);
	}
}

  最小推，MinHeap:

 

public class MinHeap<T> extends AbstractHeap<T>
{

	public MinHeap(T[] elements)
	{
		super(elements);
	}

	public MinHeap(Comparator<T> com, T[] elements)
	{
		super(com, elements);
	}

	/*
     * 注意两个参数比较的顺序
     */
	@Override
	protected int compare(int i, int j) throws NoComparableException
	{
		return super.compare(j, i);
	}

	@Override
	protected int compare(T i, T j) throws NoComparableException
	{
		return super.compare(j, i);
	}
}

 最大堆，MaxHeap:

 

public class MaxHeap<T> extends AbstractHeap<T>
{

	public MaxHeap(T[] elements)
	{
		super(elements);
	}

	public MaxHeap(Comparator<T> com, T[] elements)
	{
		super(com, elements);
	}

	/*
     * 注意两个参数比较的顺序
     */
	@Override
	protected int compare(int i, int j) throws NoComparableException
	{
		return super.compare(i, j);
	}

	@Override
	protected int compare(T i, T j) throws NoComparableException
	{
		return super.compare(i, j);
	}
}