算法练习(21) - 大顶堆

0. questtion

Build the sequence of integers using the maximum heap sort method

1. background knowledge

2 resolution

2.1 the principle

Use recursion to make each node conform to the characteristics of the heap

2.2 the code

public class BuildHeapTest{

    @Test
    public void buildHeap_test() {
        int[]  arr = {1,2,3,4,7,8,9,10,14,16};
        buildHeap(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private void buildHeap(int[] arr) {
        for (int i = arr.length; i >= 0; i--) {
            maxHeap(arr,i);
        }
    }

    private void maxHeap(int[] arr, int i) {
        int leftI = 2*(i+1) - 1;
        int rightI = 2*(i+1);
        // 没有子节点
        if(arr.length -1 < leftI && arr.length -1 < rightI){
            return;
        }
        // 只有左子节点
        if(arr.length -1 >= leftI && arr.length -1 < rightI){
            // 调整arr[i] 与 arr[leftI] 的位置
            if(arr[leftI] >= arr[i]){
                int temp = arr[leftI];
                arr[leftI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,leftI);
            }
        }
        // 左右子节点都有
        else{
            // 调整arr[i] 与 arr[leftI] 的位置
            if(arr[leftI] >= arr[i] && arr[leftI] >= arr[rightI]){
                int temp = arr[leftI];
                arr[leftI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,leftI);
            }
            // 调整arr[i] 与 arr[rightI] 的位置
            if(arr[rightI] >= arr[i] && arr[rightI] >= arr[leftI]){
                int temp = arr[rightI];
                arr[rightI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,rightI);
            }
        }

    }
}

3 Complexity analysis