堆

Reference

图解大顶堆的构建、排序过程 - 鹿呦呦 - 博客园 (cnblogs.com)

正文

突然发现没有学过堆这个结构呀
无论是王道还是王卓的课里面都没有
昨天考到了大根堆，完全不记得了
这里再学一下

这里使用大顶堆举例子:

上律: 找到最后一个非叶子节点将子节点与其对比,将更大的放到父节点

/**
 * 构建大顶堆
 * 大顶堆的性质：每个结点的值都大于或等于其左右子结点的值。
 */
function buildBigHeap(int[] arr,int len) {
    for (i = floor(len/2) - 1; i >= 0; i--) {
        //根节点小于左子树
        if (2 * i + 1 < len && arr[i] < arr[2 * i + 1]) {
            //交换根节点和左子树的值
            swap(arr, i, 2 * i + 1);
            // temp = arr[i];
            // arr[i] = arr[2 * i + 1];
            // arr[2 * i + 1] = temp;
            //检查左子树是否满足大顶堆的性质，如果不满足，则重新调整
            if ((2 * (2 * i + 1) + 1 < len && arr[2 * i + 1] < arr[2 * (2 * i + 1) + 1])
            || (2 * (2 * i + 1) + 2 < len && arr[2 * i + 1] < arr[2 * (2 * i + 1) + 2])) {
                buildBigHeap(arr, len);
            }
        }
        //根节点小于右子树
        if (2 * i + 2 < len && arr[i] < arr[2 * i + 2]) {
            //交换根节点和右子树的值
            swap(arr, i, 2 * i + 2);
            //检查右子树是否满足大顶堆的性质，如果不满足，则重新调整
            if ((2 * (2 * i + 2) + 1 < len && arr[2 * i + 2] < arr[2 * (2 * i + 2) + 1])
            || (2 * (2 * i + 2) + 2 < len && arr[2 * i + 2] < arr[2 * (2 * i + 2) + 2])) {
                buildBigHeap(arr, len);
            }
        }
    }
}