int currentNode = 1, child = 2;//当前子树的根节点索引和左孩子索引
while (child <= size) {
// 每次迭代筛选出子树的最大元素作为该子树的根节点，交换元素位置
if (child < size && heap[child].compareTo(heap[child + 1]) < 0)
child++;
if (lastElement.compareTo(heap[child]) >= 0)
break;// 已满足最大堆特性
heap[currentNode] = heap[child];
currentNode = child;
child *= 2;
}// currentNode指示当前被考察的子树根节点位置
heap[currentNode] = lastElement;
return maxElement;
}
/**
* 将输入数组（长度为n)初始化为最大堆
* 实现方法：从有孩子节点的元素开始（索引为n/2)，如果以该位置为根的子树
* 满足最大堆特性，则无需调整，否则通过交换位置进行调整。依次调整i，i-1，i-2..
* 位置为根的子树，直到数组的首元素为止。
* @param theHeap 输入的数组，可能不满足堆特性
* @param theSize 输入数组元素个数
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
public void initialize(Comparable[] theHeap, int theSize) {
heap = theHeap;
size = theSize;
for (int root = size / 2; root >= 1; root--) {
Comparable rootElement = heap[root];
while (child <= size) {
if (child < size && heap[child].compareTo(heap[child + 1]) < 0)
child++;
if (rootElement.compareTo(heap[child]) >= 0)
break;
heap[child / 2] = heap[child];
child *= 2;
}
heap[child / 2] = rootElement;
}
}
/**
* 指定格式打印堆数组[元素1，元素2，元素3...]
*/
public String toString() {
StringBuffer s = new StringBuffer();
s.append("The " + size + " elements are [");
if (size > 0) {
s.append(heap[1]);
for (int i = 2; i <= size; i++)
s.append(", " + heap[i]);
}
s.append("]");
return new String(s);
}
}