堆疊樹

// 堆疊樹(由下往上)

// (1~n) m 的子節點為 2m, 2m+1
// 階層從 1階 開始
// 每階最多 (2(level-1)次方) 個節點
let data = [26, 5, 19, 1, 61, 11, 59, 15, 48, 77];

// 最後一個有子節點的節點
let lastParentIndex = Math.floor(data.length / 2) - 1;

console.log(JSON.stringify(data));
// 往前拜訪每個有孩子的節點
for (let i = lastParentIndex; i >= 0; i--) {
    debugger;
    check(i, data);
}
console.log(JSON.stringify(data));

//----------------------------
// 檢查父節點與子節點的大小
function check(parent_index, _data) {
    debugger;

    // 會不斷往下有子節點的節點探索
    while (parent_index <= lastParentIndex) {

        let leftIndex = (parent_index + 1) * 2 - 1;
        let rightIndex = leftIndex + 1;

        // 可能沒有 right 子節點
        rightIndex = (rightIndex >= _data.length) ? null : rightIndex;

        // console.log('%d = %d',  _data[leftIndex], _data[rightIndex]);

        let maxIndex = (rightIndex == null || (_data[leftIndex] > _data[rightIndex])) ? leftIndex : rightIndex;

        if (_data[parent_index] < _data[maxIndex]) {
            // 交換
            let temp = _data[maxIndex];
            _data[maxIndex] = _data[parent_index];
            _data[parent_index] = temp;
        }

        // 往下層比較
        // 確定變動的節點要比他的子節點大
        parent_index = maxIndex;
    }
}
------------------------------------------------------------------------
// 堆疊樹(由上往下)

// (1~n) m 的子節點為 2m, 2m+1
// 階層從 1階 開始
// 每階最多 (2(level-1)次方) 個節點
let data = [26, 5, 19, 1, 61, 11, 59, 15, 48, 77];

console.log(JSON.stringify(data));
// 往前拜訪每個有孩子的節點
for (let i = 0; i < data.length; i++) {
    debugger;
    check(i, data);
}
console.log(JSON.stringify(data));

//----------------------------
// 檢查父節點與子節點的大小
function check(parent_index, _data) {
    debugger;

    let prev_index;

    // 會不斷往下有子節點的節點探索
    while (parent_index >= 0) {


        if (prev_index != null) {
            // 回朔 只需比對上一個子節點
            if (_data[parent_index] < _data[prev_index]) {
                // 交換
                let temp = _data[prev_index];
                _data[prev_index] = _data[parent_index];
                _data[parent_index] = temp;
            }

        } else {
            // 第一次進入

            let leftIndex = (parent_index + 1) * 2 - 1;
            let rightIndex = leftIndex + 1;

            leftIndex = (leftIndex >= _data.length) ? null : leftIndex;
            rightIndex = (rightIndex >= _data.length) ? null : rightIndex;


            if (leftIndex == null && rightIndex == null) {
                // 都沒有子節點
                return;
            }

            console.log('%d(%d,%d)', _data[parent_index], _data[leftIndex], _data[rightIndex]);

            let maxIndex = (rightIndex == null || (_data[leftIndex] > _data[rightIndex])) ? leftIndex : rightIndex;

            if (_data[parent_index] < _data[maxIndex]) {
                // 交換
                let temp = _data[maxIndex];
                _data[maxIndex] = _data[parent_index];
                _data[parent_index] = temp;
            }
        }
        //-----------------------
        prev_index = parent_index;
        // 往下層比較
        // 確定變動的節點要比他的子節點大
        let nextCheckIndex = Math.floor((parent_index + 1) / 2) - 1;

        if (nextCheckIndex == parent_index && parent_index == 0) {
            // 只為了解決無限迴圈
            return;
        }

        // 往上
        parent_index = nextCheckIndex;
    }
}