Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
public class Heap<T extends Comparable<T>> {
    private int capacity;
    private T[] heap;
    private int size;

    public Heap(int capacity) {
        this.capacity = capacity;
        heap = (T[]) new Comparable[capacity];
    }

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

    public void insert(T t) {
        resize();
        heap[size++] = t;
        reheapUp(size - 1);
    }

    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return heap[0];
    }

    public T deleteMin() {
        if (isEmpty()) {
            return null;
        }
        T ret = peek();
        heap[0] = heap[size - 1];
        heap[size - 1] = null;
        size--;
        reheapDown(0);
        resize();
        return ret;
    }

    public T delete(T t) {
        if (isEmpty()) {
            return null;
        }

        for (int i = 0; i < heap.length; i++) {
            if (heap[i].equals(t)) {
                heap[i] = heap[size - 1];
                heap[size - 1] = null;
                size--;
                reheapDown(i);
                resize();
                return t;
            }
        }
        return null;
    }

    public void printHeap() {
        for (int i = 0; i < heap.length; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    private void reheapUp(int i) {
        T tmp = heap[i];

        while (i > 0 && tmp.compareTo(heap[getParentIndex(i)]) < 0)
        {
            swap(i, getParentIndex(i));
            i = getParentIndex(i);
        }
    }

    private void reheapDown(int i) {
        while (hasLeftChild(i)) {
            int leftChildIndex = getLeftIndex(i);
            int smallerChildIndex = leftChildIndex;

            if (hasRightChild(i)) {
                if (heap[getRightIndex(i)].compareTo(heap[leftChildIndex]) < 0) {
                    smallerChildIndex = getRightIndex(i);
                }
            }

            if (heap[i].compareTo(heap[smallerChildIndex]) > 0) {
                swap(i, smallerChildIndex);
            } else {
                break;
            }

            i = smallerChildIndex;
        }
    }

    private int getParentIndex(int n) {
        return (n - 1) / 2;
    }

    private int getLeftIndex(int n) {
        return 2 * n + 1;
    }

    private int getRightIndex(int n) {
        return 2 * n + 2;
    }

    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private boolean hasLeftChild(int index) {
        return (2 * index + 1) <= (size - 1);
    }

    private boolean hasRightChild(int index) {
        return (2 * index + 2) <= (size - 1);
    }

    private void resize() {
        if (size == capacity) {
            heap = Arrays.copyOf(heap, capacity * 2);
        } else if (size == capacity / 4) {
            heap = Arrays.copyOf(heap, capacity / 2);
        }
        capacity = heap.length;
    }
}
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.