大根堆的创建（视频讲解）

大根堆的创建2

注意：

1. 其实左右节点 都是要去找父亲节点，不如遍历的时候，就通过父亲节点遍历（可以减少遍历次数以及 遍历经过中的循环次数）

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

public class TestHeap {
    

    public int[] elem;
    public int usedSize;//当前堆当中的有效的元素的数据个数

    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 每棵子树的根节点的下标 * @param len 每棵子树的结束位置 */

    private void shiftDown(int parent ,int len) {
    
        int child = 2 * parent + 1;
        //最起码是有左孩子
        while (child < len) {
    
            //判断 左孩子 和 右孩子 谁最大,前提是 必须有 右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
    
                child++;//此时 保存了最大值的下标
            }
            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;
    }
}