MinHeap.java

package util;

import java.util.ArrayList;
import java.util.List;

public abstract class MinHeap<T> {
	private int sizeLimit;
	private int size;
	private List<T> heap;

	public MinHeap() {
		size = 0;
		sizeLimit = 0;
		heap = new ArrayList<T>();
	}

	public MinHeap(int sizeLimit) {
		size = 0;
		setSizeLimit(sizeLimit);
		heap = new ArrayList<T>();
	}

	public MinHeap(List<T> data) {
		size = data.size();
		sizeLimit = 0;
		heap = new ArrayList<T>(data);
		adjust();
	}

	public MinHeap(T[] data) {
		size = data.length;
		sizeLimit = 0;
		heap = new ArrayList<T>();
		for (T item : data) {
			heap.add(item);
		}
		adjust();
	}

	public MinHeap(List<T> data, int sizeLimit) {
		size = data.size();
		setSizeLimit(sizeLimit);
		heap = new ArrayList<T>(data);
		adjust();
		while (sizeLimit != 0 && size > sizeLimit) {
			pop();
		}
	}

	public MinHeap(T[] data, int sizeLimit) {
		size = data.length;
		setSizeLimit(sizeLimit);
		heap = new ArrayList<T>();
		for (T item : data) {
			heap.add(item);
		}
		adjust();
	}

	private void adjust() {
		int pos = (size - 2) / 2;
		int cSize = size;
		while (pos >= 0) {
			siftDown(pos, cSize - 1);
			pos--;
		}
	}

	private void siftDown(int i, int m) {
		T t = heap.get(i);
		for (int j = 2 * i + 1; j <= m; j = 2 * j + 1) {
			if (j < m && compare(heap.get(j), heap.get(j + 1)) > 0) {
				j++;
			}
			if (compare(t, heap.get(j)) <= 0) {
				break;
			} else {
				heap.set(i, heap.get(j));
				i = j;
			}
		}
		heap.set(i, t);
	}

	private void siftUp(int start) {
		T t = heap.get(start);
		int j = start;
		int i = (j - 1) / 2;
		while (j > 0) {
			if (compare(heap.get(i), t) <= 0) {
				break;
			} else {
				heap.set(j, heap.get(i));
				j = i;
				i = (i - 1) / 2;
			}
		}
		heap.set(j, t);
	}

	public int getSize() {
		return size;
	}

	public int getSizeLimit() {
		return sizeLimit;
	}

	public void setSizeLimit(int sizeLimit) {
		this.sizeLimit = sizeLimit <= 0 ? 0 : sizeLimit;
	}

	// a > b return 1;
	// a == b return 0;
	// a < b return -1;
	protected abstract int compare(T t1, T t2);

	public List<T> data() {
		return heap;
	}

	public T pop() {
		if (size == 0)
			return null;
		T rt = heap.get(0);
		heap.set(0, heap.get(size - 1));
		size--;
		siftDown(0, size - 1);
		return rt;
	}

	public boolean push(T item) {
		if (sizeLimit != 0 && size >= sizeLimit) { // to limit
			// pop & push
			if (compare(item, heap.get(0)) > 0) {
				if (size < heap.size()) {
					heap.set(size, item);
				} else {
					heap.add(item);
				}
				siftUp(size);
				size++;
				pop();
			}
		} else { // just add it
			if (size < heap.size()) {
				heap.set(size, item);
			} else {
				heap.add(item);
			}
			siftUp(size);
			size++;
		}
		return true;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		heap = new ArrayList<T>();
		size = 0;
	}

	public static void main(String[] args) {
		List<Integer> myList = new ArrayList<Integer>();
		myList.add(9);
		myList.add(200);
		MinHeap<Integer> h = new MinHeap<Integer>(myList, 1) {
			@Override
			protected int compare(Integer t1, Integer t2) {
				return t2.compareTo(t1);
			}
		};
		h.push(8);
		h.push(1);
		h.push(6);
		h.push(3);
		while (!h.isEmpty()) {
			System.out.println(h.pop());
		}
	}
}