Trung tâm cá nhân
sách gpt4 ai đã đi

javascript - MAX_HEAPIFY 实现

In lại 作者：行者123 更新时间：2023-11-29 11:03:46 27 4
mua khóa gpt4 Nike

我编写了 JavaScript 代码来构建一个维护最大堆属性的最大堆化，但我对实现有很多疑问:

array I test on: [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

当我对数组排序时进行测试时，我得到:

[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ]

虽然未排序我得到:

[ 16, 14, 8, 9, 10, 2, 3, 4, 7, 1 ]

为什么 max-heapify 会受到正在排序的数组的影响？

我发现当数组排序后解决方案是:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

即使我发现我的实现根据 CLRS 中的伪代码是正确的，为什么当数组排序时我得到了不同的解决方案？

您能否指定另一个不使用递归同时实现相同功能的过程？

function BuildMaxHeap(array){
 for(var i = Math.floor(array.length / 2); i >= 0; i--){
    MAX_HEAPIFY(array, i);
 }
 return array;
}

function MAX_HEAPIFY(array, i) {
 var left = 2 * i + 1;
 var right = 2 * i + 2;
 var largest = i;
 if(left <= array.length && array[left] > array[largest]){
    largest = left;
  }
 if(right <= array.length && array[right] > array[largest]){
    largest = right;
 }
 if(largest != i){
    var temp = array[i];
    array[i] = array[largest];
    array[largest] = temp;
    MAX_HEAPIFY(array, largest);
 }
}

1 Câu trả lời

正如您所注意到的，由一组数字组成的最小/最大堆的叶子可以有多种配置，具体取决于它们的插入顺序。

您可能认为叶子的这种“全局排序”可能源于底层堆属性的某些突发行为，但给定的数组与特定配置没有一对一的对应关系。

发生这种情况是因为插入子项并向上冒泡(与父项交换)的方式，一旦它小于父项就会停止 - 其中可以有多个有效候选者堆中的一个位置。

当我第一次实现堆时，这也让我感到困惑。

关于javascript - MAX_HEAPIFY 实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42742930/

27 4 0
Bài viết được đề xuất: javascript - D3 : How to use exit(). 多系列折线图的 remove()
Bài viết được đề xuất: javascript - 为什么我的数组的最后一个元素被替换为 0
Bài viết được đề xuất: javascript - 用于新项目的 Polymer 2.x 或 1.x
Bài viết được đề xuất: mysql - Doctrine - 自动插入行关联表
行者123
Hồ sơ cá nhân

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá Didi Taxi miễn phí
Mã giảm giá Didi Taxi
Các bài viết nóng hổi trên toàn bộ trang web
Giấy chứng nhận ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com