Javascript 中的迷你堆排序实现

Question

我想使用 MinHeap 在 Javascript 中实现堆排序算法。 但代码输出不正确...

我的数据集有 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] + ',');
    }
}

请帮助我找出这段代码有什么问题......真的感谢您的帮助！

Answer 1

heapify

有这些问题：

• 由于数组的第一个索引为 0，因此“公式”

  left = 2 * i

  是错误的；它会说根的左子节点（在 0 处）是... 0。您需要

  left = 2 * i + 1

  和

  right = 2 * i + 2

  。

• 您有一个

  else

  ，后跟比较表达式。这并不像你想象的那样。你需要

  else if

• if ... else

  结构不包括如果节点只有左子节点（即当

  left == n

  时）要做什么。目前，您的代码假设最小的位于

  i

  ，但您从不检查这是否属实。

在

buildMinHeap

有这个问题：

• 当节点数为偶数时，循环不会从正确的索引处开始。例如，如果有 4 个节点，则

  n

  将设置为 3，循环将从 0 开始。这是错误的。它应该从 1 开始，因为 1 是位于

  n

  的节点的父节点。

不是问题，但是

• 如果你有

  right <= n

  ，那么测试

  left <= n

  是没有用的：如果第一个为真，那么第二个也保证为真，因为

  left

  比

  right

  少一个。

• heapify

  不应该返回任何东西。突变就地发生。

• 评论不应该说诸如

  // Build min-heap function

  之类的琐碎事情。这对读者没有帮助。相反，提供评论来解释“为什么？”。

以下是对这两个函数的更正：

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

    // Check if left child has smaller value: if so, select it
    if (left <= n && data[left] < data[smallest]) {
        smallest = left;
    }
    // Check if right child has even smaller value: if so, select it
    if (right <= n && data[right] < data[smallest]) {
        smallest = right;
    }
    // If either child has the smallest value, swap and repeat
    if (smallest != i) {
        [data[i], data[smallest]] = [data[smallest], data[i]];
        heapify(data, smallest, n);
    }
}

function buildMinHeap(data) {
    const n = data.length - 1;
    // Iterate all *internal* nodes from bottom to top
    for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
        heapify(data, i, n);
    }
}

最后，这不是堆排序的实现。这仅构建堆。堆不是一个排序数组，而是一种确保堆属性的数据结构。这对于包括堆排序在内的多种算法很有用。为了实现堆排序，您需要不断从堆中提取最小值，直到堆为空。您可以将提取的值保存在数组中不再被收缩堆使用的部分中。

因此，您仍然需要实现从堆中提取值的函数，以及通过重复调用该函数直到堆为空来对数组进行排序的函数。