public T deleteMax() {
		T res = array.get(0); // O(1)
		array.set(0, array.get(array.size() - 1)); // O(1)
		array.remove(array.size() - 1); // O(1)
		int index = 0;
		while (index < array.size()) {
			int left = index * 2 + 1;
			int right = index * 2 + 2;
			if (right > array.size()) {
				break;
			} else if (right < array.size()) {
				int larger = array.get(left).compareTo(array.get(right)) > 0 ? left
						: right;
				if (array.get(index).compareTo(array.get(larger)) < 0) {
					this.swap(index, larger);
					index = larger;
				} else {
					break;
				}

			} else {// only have left children.
				if (array.get(index).compareTo(array.get(left)) < 0) {
					this.swap(index, left);
					index = left;
				} else {
					break;
				}

			}

		}
		return res;
	}