- }
- }
- public int popTop() {
- // 弹出树根, 即最大元素
- if(this.currentIndex!=0) {
- int popValue = this.Array[0];
- this.Array[0] = this.Array[--this.currentIndex];
- this.moveDown(0); // 向下移动元素 从树根到树脚方向
- return popValue;
- }else {
- return -1;
- }
- }
- private void moveUp(int index) {
- int temp = this.Array[index];
- int root = (index-1)/2;
- while(index>0&&temp>this.Array[root]) {
- // 判断元素所在位置, 防止越界; 同时检查插入元素和其相对树根元素的大小
- this.Array[index] = this.Array[root];
- index = root;
- root = (index-1)/2;
- }
- this.Array[index] = temp;
- }
- private void moveDown(int index) {
- int temp = this.Array[index];
- int largeValue;
- while(this.currentIndex/2>index) {
- // 每次循环的子树都必须要至少有一个子节点 (左节点)
- int left = 2*index+1;
- int right = left+1;
- if(right<this.currentIndex&&this.Array[left]<this.Array[right]) {
- // 保证有右节点存在, 并从左节点和右节点中选择较大的节点
- largeValue = right;
- }else{
- largeValue = left;
- }
- if(temp>this.Array[largeValue]) {
- break;
- }else {
- this.Array[index] = this.Array[largeValue];
- index=largeValue;
- }
- }
- this.Array[index] = temp;
- }
来源: http://www.bubuko.com/infodetail-3002824.html