Java实现堆排序（大根堆）(2)

//删除堆顶元素操作
    public int[] deleteMax(int[] array){
        //将堆的最后一个元素与堆顶元素交换，堆底元素值设为-99999
        array[0] = array[array.length-1];
        array[array.length-1] = -99999;
        //对此时的根节点进行向下调整
        adjustDownToUp(array, 0, array.length);
        return array;
    }

对堆的插入操作：先将新节点放在堆的末端，再对这个新节点执行向上调整操作。

假设数组的最后一个元素array[array.length-1]为空，新插入的结点初始时放置在此处。

//插入操作:向大根堆array中插入数据data
    public int[] insertData(int[] array, int data){
        array[array.length-1] = data; //将新节点放在堆的末端
        int k = array.length-1;  //需要调整的节点
        int parent = (k-1)/2;    //双亲节点
        while(parent >=0 && data>array[parent]){
            array[k] = array[parent];  //双亲节点下调
            k = parent;
            if(parent != 0){
                parent = (parent-1)/2;  //继续向上比较
            }else{  //根节点已调整完毕，跳出循环
                break;
            }
        }
        array[k] = data;  //将插入的结点放到正确的位置
        return array;
    }

测试：

public void toString(int[] array){
        for(int i:array){
            System.out.print(i+" ");
        }
    }
   
    public static void main(String args[]){
        HeapSort hs = new HeapSort();
        int[] array = {87,45,78,32,17,65,53,9,122};
        System.out.print("构建大根堆：");
        hs.toString(hs.buildMaxHeap(array));
        System.out.print("\n"+"删除堆顶元素：");
        hs.toString(hs.deleteMax(array));
        System.out.print("\n"+"插入元素63:");
        hs.toString(hs.insertData(array, 63));
        System.out.print("\n"+"大根堆排序：");
        hs.toString(hs.heapSort(array));   
    }

1 构建大根堆：122 87 78 45 17 65 53 9 32
2 删除堆顶元素：87 45 78 32 17 65 53 9 -99999
3 插入元素63:87 63 78 45 17 65 53 9 32
4 大根堆排序：9 17 32 45 53 63 65 78 87