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?）。这意味着，当我们调用递归函数时，必须对其进行分配，并且递归函数必须返回某些内容。

在heapify中，我们必须返回array。同样，每次对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