算法笔记 #004# 堆（重写）

留着备用。
Heap是一种满足特定性质的数组，如下：
<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
    </head>
    <body>
        <textarea id="data-area" rows="25" cols="80" placeholder="paste your data here..."></textarea>
        <p><button id="run">run code</button></p>
        
        <script type="text/javascript">
            let btn = document.querySelector("#run");
            btn.addEventListener("click", handleClick);

            function handleClick() {
                let dataArea = document.querySelector('#data-area');
                let data = dataArea.value;
                let arr = CommonUtil.handleData(data);
                // 样例输入：2 8 1 14 7 9 3 10 4 16
                console.log('before:', arr);
                Heap.buildMaxHeap(arr);
                console.log('after:', arr);
            }            
        </script>
        
        <script type="text/javascript">
            class CommonUtil {
                static handleData(data) {
                    let result = [];
                    let digit = /-?d+/g;
                    let match;
                    while(match = digit.exec(data)) {
                        result.push(Number(match[0]));
                    }
                    return result;
                }    
            }
        </script>
        
        
        <script type="text/javascript">
            class Heap {
                // 把数组A转化为最大堆
                static buildMaxHeap(A) {
                    A.unshift(undefined); // 便于后续的下标计算
                    
                    A.heapSize = A.length - 1; // 实际多存了一个undefined
                    for (let i = Math.floor(A.heapSize / 2); i >= 1; --i) {
                        // 对所有非叶结点调用一次maxHeapify
                        // 之所以下标从后往前，是因为maxHeapify假定调用结点的左右子树都已经为最大堆
                        // 单个元素（叶结点）很自然地是一个最大堆
                        Heap.maxHeapify(A, i);
                    }
                }
                
                // 维护堆的性质
                static maxHeapify(A, i) {
                    let l = Heap.left(i);
                    let r = Heap.right(i);
                    
                    let largest = i;
                    // maxHeapify假定调用结点的左右子树都已经为最大堆
                    // 只是把调用结点i放到恰当的位置，以维护堆的性质
                    if (l <= A.heapSize && A[l] > A[i]) {
                        largest = l;
                    }
                    
                    if (r <= A.heapSize && A[r] > A[largest]) {
                        largest = r;
                    }
                    
                    if (largest != i) {
                        A[largest] = A[i] + A[largest];
                        A[i] = A[largest] - A[i];
                        A[largest] = A[largest] - A[i];
                        Heap.maxHeapify(A, largest);
                    }
                }
                
                static left(i) {
                    return 2 * i;
                }
                
                static right(i) {
                    return 2 * i + 1;
                }
            }
        </script>
    </body>
</html>