Heap Data structure and Heap Sort implementation

Heap.java

package com.abhi.ds.heap;

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

public class Heap<T extends Comparable<T>> {

	private List<T> items;

	public Heap() {
		items = new ArrayList<T>();
	}
	
	/**
	 * Adds item to the list that backs heap implementation
	 * @param item
	 */
	public void addItem(T item) {
		items.add(item);
	}

	/**
	 * Inserts element to an existing heap maintaining the proper heap order
	 * @param item
	 */
	public void insert(T item) {
		items.add(item); //insert item at the end
		siftUp(); //siftUp to maintain heap order
	}

	/**
	 * Removes the top element(with max value) from the heap
	 * @param item
	 * @return hold
	 */
	public T delete() {
		if (items.isEmpty()) {
			throw new NoSuchElementException();
		}

		if (items.size() == 1) {
			return items.remove(0);
		}

		T hold = items.get(0);
		items.set(0, items.remove(items.size() - 1));
		siftDown(0, items.size() - 1);
		return hold;
	}

	public void sort() {
		if(items.isEmpty()) {
			throw new IllegalStateException("Build heap and add items to it before calling sort...");
		}
		heapify(); // place items in a max heap order
		int end = items.size() - 1;
		while (end > 0) {
			/*
			 * swap the root (max value) of the heap with the last element of
			 * the heap
			 */
			swap(0, end);
			/*
			 * decrease the size of the heap by one so that the previous max
			 * value will stay in its proper placement)
			 */
			end = end - 1;
			// put the heap back in max-heap order
			siftDown(0, end);

		}
	}

	private void heapify() {
		int start = (items.size() - 2) / 2; // the index in items of the last parent node
												
		int end = items.size() - 1;
		while (start >= 0) {
			/*
			 * sift down the node at index start to the proper place such that
			 * all nodes below the start index are in heap order
			 */
			siftDown(start, end);
			if(start == 0) break;
			start = start - 1; // visit next parent approaching root (the first
								// parent)
		}

	}

	private void siftUp() {
		int k = items.size() - 1;
		while (k > 0) {
			int p = (k - 1)/ 2;
			T item = items.get(k);
			T parent = items.get(p);
			if (item.compareTo(parent) > 0) {
				swap(k, p);
				// move up one level
				k = p;
			} else {
				break; // break if item <= parent
			}

		}
	}

	private void siftDown(int start, int end) {
		int root = start;
		int l = 2*root+1; //left child
		while (l <= end) { // while root has at least one child
			
			int r = l + 1; //right child
			int max = l;

			/*Find max among root, left child and right child 
			 * if the max is not the root node do a swap with max(left child, right child)
			 */
			if (r <= end) { //there is a right child
				if (items.get(r).compareTo(items.get(l)) > 0) {
					max++;
				}
			}
			if (items.get(root).compareTo(items.get(max)) < 0) {
				// swap
				swap(root, max);
				root = max;
				l = 2 * root + 1; 
			} else {
				break;
			}
		}
	}

	private void swap(int k, int p) {
		T temp = items.get(k);
		items.set(k, items.get(p));
		items.set(p, temp);
	}
	
	public int size() {
		return items.size();
	}
	
	public boolean isEmpty(){
		return items.isEmpty();
	}

	public String toString() {
		return items.toString();
	}
}