The creation of a large root heap (video explanation)

大根堆的创建2

注意：

1. In fact, the left and right nodes They are all going to find the parent node,than when traversing,Just traverse through the parent node（The number of traversals can be reduced as well The number of loops in the traversal pass）

for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--)

public class TestHeap {
    

    public int[] elem;
    public int usedSize;//The number of valid elements in the current heap

    public TestHeap() {
    
        this.elem = new int[10];
        this.usedSize = 0;
    }

    public void initArray(int[] array) {
    
        elem = Arrays.copyOf(array,array.length);
        usedSize = elem.length;
    }

    /** * 建堆:【大根堆】 * 时间复杂度：O(n) */

    public void createHeap() {
    
        for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
    
            shiftDown(parent,usedSize);
        }
    }

    /** * 实现 向下调整 * @param parent The subscript of the root node of each subtree * @param len 每棵子树的结束位置 */

    private void shiftDown(int parent ,int len) {
    
        int child = 2 * parent + 1;
        //At least there are left children
        while (child < len) {
    
            //判断 左孩子 和 右孩子 谁最大,前提是 必须有 右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
    
                child++;//此时 The subscript of the maximum value is stored
            }
            if(elem[child] > elem[parent]) {
    
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
    
                break;
            }
        }
    }

    private void swap(int[] array,int i,int j) {
    
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}