JavaScript实现MinHeap堆排序输出异常，求代码问题排查

问题描述 #

尝试用JavaScript基于MinHeap实现堆排序，但输出结果不正确，数据集包含1000个数字，以下是实现代码：

import * as fs from 'fs';

// Read the input file
const input = fs.readFileSync('data.txt', 'utf8');
let data = input.split(" ").map(Number);

// Call the main function to build the min-heap and print the results
main(data);

// Min-heapify function
function heapify(data, i, n) {
    let left = 2 * i;
    let right = 2 * i + 1;
    let smallest = i;

    if (right <= n && left <= n && data[right] < data[left]) {
        if (data[right] < data[i]) {
            smallest = right;
        }
    }
    else (right <= n && left <= n && data[right] > data[left])
    {
        if (data[left] < data[i]) {
            smallest = left;
        }
    }
    //if smallest is changed to original left or right
    if (smallest != i) {
        // Swap data[i] and data[smallest]
        [data[i], data[smallest]] = [data[smallest], data[i]];

        //Recursively heapify the subtree
        heapify(data, smallest, n);
    }
    return data;
}

// Build min-heap function
function buildMinHeap(data) {
    const n = data.length - 1;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(data, i, n);
    }
}

// Main function
function main(data) {

    // Build a min-heap
    buildMinHeap(data);

    // Print the first 20 values data[1], data[2], ..., data[20]
    console.log("First 20 values:");
    const n = data.length;
    for (let i = 0; i <= 19 && i <= n; i++) {
        process.stdout.write(data[i] + ',');
    }

    console.log("Last 20 values:");
    for (let i = n - 1; i >= n - 20 && i >= 1; i--) {
        process.stdout.write(data[i] + ',');
    }
}

问题排查与修正 #

1. 堆索引逻辑错误 #

堆的索引计算混淆了1-based和0-based规则：

• 原代码中left = 2 * i、right = 2 * i + 1是1索引的计算方式，但JavaScript数组采用0索引，正确的子节点索引应为：

  let left = 2 * i + 1;
  let right = 2 * i + 2;
  

• buildMinHeap中循环起始值错误，正确的非叶子节点起始索引应为Math.floor(data.length / 2) - 1，无需额外对n做减1处理。

2. Heapify函数条件判断漏洞 #

• else后不能直接跟条件，应改为else if；且原逻辑未覆盖仅左孩子存在或仅右孩子存在的场景。正确的判断逻辑应先找出左、右孩子中的最小值，再与当前节点比较：

  // 比较左孩子与当前最小值
  if (left <= n && data[left] < data[smallest]) {
      smallest = left;
  }
  // 比较右孩子与当前最小值
  if (right <= n && data[right] < data[smallest]) {
      smallest = right;
  }
  

3. BuildMinHeap循环范围错误 #

原代码中n = data.length - 1后，循环起始值Math.floor(n / 2) - 1会导致跳过部分非叶子节点，正确的循环范围应为从最后一个非叶子节点开始遍历到根节点：

function buildMinHeap(data) {
    const n = data.length - 1;
    // 从最后一个非叶子节点开始堆化
    for (let i = Math.floor(data.length / 2) - 1; i >= 0; i--) {
        heapify(data, i, n);
    }
}

4. 输出逻辑修正 #

原代码打印的是data[0]到data[19]，但注释说明要打印data[1]到data[20]，需调整循环起始值：

// 打印data[1]到data[20]
for (let i = 1; i <= 20 && i < data.length; i++) {
    process.stdout.write(data[i] + ',');
}

完整修正代码 #

import * as fs from 'fs';

// Read the input file
const input = fs.readFileSync('data.txt', 'utf8');
let data = input.split(" ").map(Number);

// Call the main function to build the min-heap and print the results
main(data);

// Min-heapify function
function heapify(data, i, n) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;

    // 比较左孩子与当前最小值
    if (left <= n && data[left] < data[smallest]) {
        smallest = left;
    }
    // 比较右孩子与当前最小值
    if (right <= n && data[right] < data[smallest]) {
        smallest = right;
    }

    if (smallest !== i) {
        [data[i], data[smallest]] = [data[smallest], data[i]];
        heapify(data, smallest, n);
    }
    return data;
}

// Build min-heap function
function buildMinHeap(data) {
    const n = data.length - 1;
    // 从最后一个非叶子节点开始堆化
    for (let i = Math.floor(data.length / 2) - 1; i >= 0; i--) {
        heapify(data, i, n);
    }
}

// Main function
function main(data) {
    buildMinHeap(data);

    // Print the first 20 values data[1], data[2], ..., data[20]
    console.log("First 20 values:");
    const len = data.length;
    for (let i = 1; i <= 20 && i < len; i++) {
        process.stdout.write(data[i] + ',');
    }
    console.log('\n');

    console.log("Last 20 values:");
    for (let i = len - 1; i >= len - 20 && i >= 1; i--) {
        process.stdout.write(data[i] + ',');
    }
}

内容的提问来源于stack exchange，提问作者Coco