) { //判断堆是否为空
return currentSize == 0;
}
//插入一个节点
public boolean insert(int key) {
if(currentSize == maxSize) return false; //已满 不能插入
Node newNode = new Node(key);
heapArray[currentSize] = newNode; //先插入到最后
trickleUp(currentSize++); //从该节点开始向上筛选,并把currentSize的值加1
return true;
}
//删除一个最大节点(根)
public Node remove() {
Node root = heapArray[0];//移除根节点
heapArray[0] = heapArray[--currentSize];//最后一个节点移动到根节点的位置
trickleDown(0); //向下筛选
return root;
}
//向上筛选
private void trickleUp(int index) {
int parent = (index-1)/2; //先找到父节点索引
Node bottom = heapArray[index];
while(index >0 && heapArray[parent].getKey() < bottom.getKey()) {
//只要index>0且父节点的数据项的值小于自己的值 就继续向上
heapArray[index] = heapArray[parent];
index = parent;
parent = (index-1)/2;
}
heapArray[index] = bottom;
}
//向下筛选
private void trickleDown(int index) {
int largeChild;
Node top = heapArray[index];
while(index < currentSize/2) { //只要不是叶节点 就继续向下筛选
//首先获得其左右孩子节点中数值大的那个节点的下标
int left = index*2+1;
int right = index*2+2;
if(right < currentSize && heapArray[left].getKey() < heapArray[right].getKey()) {
largeChild = right;
}else {
largeChild = left;
}
//进行值的比较,把值大的子节点与该节点互换,并对值最大的那个节点再继续向下筛选
if(top.getKey() >= heapArray[largeChild].getKey()) break;
else {
heapArray[index] = heapArray[largeChild];
index = largeChild;
&nbs