在 R 中实现 Heapsort 算法的问题

Question

我想在 R 中创建自己的 Heapsort 算法。
那是我的代码

heapify <- function(array, n, i)
{
  parent <- i
  leftChild <- 2 * i + 1
  rightChild <- 2 * i + 2

  if ((leftChild < n) & (array[parent] < array[leftChild]))
  {
    parent = leftChild
  }

  if ((rightChild < n) & (array[parent] < array[rightChild]))
  {
    parent = rightChild
  }

  if (parent != i)
  {
    array = replace(array, c(i, parent), c(array[parent], array[i]))
    heapify(array, n, parent)
  }
}

heapSort <- function(array)
{
  n <- length(array)

  for (i in (n+1):1)
  {
    heapify(array, n, i)
  }

  for (i in n:1)
  {
    array = replace(array, c(i, 0), c(array[0], array[i]))
    heapify(array, i, 1)
  }
  print(array)
}

但是，该实现似乎不正确。这是输入和输出的示例。

array <- c(5, 14, 3, 70, 64)
heapSort(array)

Output: [1]  5 14  3 70 64

我折腾了好久，也不知道问题出在哪里。我将不胜感激任何提示或提示。

Answer 1

我的猜测是您试图转换发布在 GeeksforGeeks 上的算法，他们在许多零基础语言中实现了该算法。这是您问题的根源之一（R 从 1 而不是 0 开始索引）。

基础零索引问题：

示例 1：

                         ## We also need to swap these indices
array = replace(array, c(i, 0), c(array[0], array[i]))
heapify(array, i, 1)

Should be:

array <- replace(array, c(i, 1), array[c(1, i)])
array <- heapify(array, i, 1)

示例 2：

leftChild <- 2 * i + 1
rightChild <- 2 * i + 2

Should be:

leftChild <- 2 * (i - 1) + 1
rightChild <- 2 * (i - 1) + 2

通过引用假设

在 R 中，您不能通过引用传递对象（请参阅此问答 Can you pass-by-reference in R?）。这意味着当我们调用递归函数时，我们必须给它赋值，而递归函数必须 return something.

在heapify中我们必须returnarray。此外，每次调用 heapify 我们都必须将 array 分配给输出。

修改后的代码如下：

heapify <- function(array, n, i)
{
    parent <- i
    leftChild <- 2 * (i - 1) + 1
    rightChild <- 2 * (i - 1) + 2

    if ((leftChild < n) & (array[parent] < array[leftChild]))
    {
        parent <- leftChild
    }

    if ((rightChild < n) & (array[parent] < array[rightChild]))
    {
        parent <- rightChild
    }

    if (parent != i) {
        array <- replace(array, c(i, parent), array[c(parent, i)])
        array <- heapify(array, n, parent)
    }

    array
}

heapSort <- function(array)
{
    n <- length(array)

    for (i in floor(n / 2):1) {
        array <- heapify(array, n, i)
    }

    for (i in n:1) {
        array <- replace(array, c(i, 1), array[c(1, i)])
        array <- heapify(array, i, 1)
    }

    array
}

这里有一些测试（注意这个算法在 R 中效率极低。不要尝试比下面大得多的向量）：

array <- c(5, 14, 3, 70, 64)
heapSort(array)
[1]  3  5 14 64 70

set.seed(11)
largerExample <- sample(1e3)

head(largerExample)
[1] 278   1 510  15  65 951

identical(heapSort(largerExample), 1:1e3)
[1] TRUE

在 R 中实现 Heapsort 算法的问题

Problems with an implementation of Heapsort algorithm in R

algorithm

r

heapsort

基础零索引问题：

通过引用假设