Problems implementing Heapsort algorithm in R

My guess is that you are trying to convert the algorithm posted on GeeksforGeeks where they implement it in many zero-based languages . This is one of the sources of the problem (R starts indexing at 1 instead of 0).

Basic zero index problem:

Example 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)

Example 2:

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

Should be:

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

Assumptions by reference

In R, you cannot pass objects by reference (see this question and answer, Can you pass by reference in R ? ). This means, when we call a recursive function, it must be allocated, and the recursive function must return something.

Before heapifywe must return array. Likewise, every call to heapifyus must be assigned arrayto an output.

Here is the modified code:

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
}

Here are some tests (note that this algorithm is extremely inefficient in R. Don't try to use a much larger vector than below):

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