Ruby Heapsort: `sink': undefined method `>' for nil:NilClass

Question

I'm currently working on Robert Sedgewicks Algorithm's book. I'm trying to implement Heap sort but I'm coming across an error

'sink': undefined method >' for nil:NilClass

This error happens because of the when the array is pass to the sort method it has 11 elements at 0 index. when it swaps index n (the number of elements in the array) with 1 is comparing nil with a string. Meaning n is 11 but there is no 11 index because the array index starts at 0.

Here is the Java implementation for the Heap sort method in the book:

 public static void sort(Comparable[] a)
  {
     int N = a.length;
     for (int k = N/2; k >= 1; k--)
        sink(a, k, N);
     while (N > 1)
     {
        exch(a, 1, N--);
        sink(a, 1, N);
     }
}
 

Now here is the implementation in Ruby:

  def sort(a)
    n = a.length
    k = n/2
    while k >= 1
      sink(a, k, n)
      k -= 1
    end
    
    while n > 1
      swap(a, 1, n)
      n -= 1
      sink(a, 1, n)
    end
    a
  end

Now, in the book the array disregards the position a[0] and starts at a[1] but I'm a bit unclear how that is being done in the sort method in the Java implementation. It is also a bit strange to me that the method would required to be pass an array starting at index 1. So my understanding is that the sort method in the Java implementation will set the array.

Notice in the example how the first element in the array starts at index 1 a[1]. Is this being done in the sort method? Meaning rearranging the array to start at index 1?

Is the Ruby implementation of sort in Ruby correct? Or is there an error?

Full implementation of Heap sort.

class Heap
  # Trickledown
  def sink(a, k, n)
    while 2 * k <= n
      j = 2 * k # child

      if !a[j + 1].nil? # check if there is a right child
        j += 1 if j > 1 && less(a, j, j + 1) # if left child less than right child
      end

      break if !less(a, k, j) # If parent greater than child break

      swap(a, k, j)
      k = j
    end
  end

  def sort(a)
    n = a.length
    k = n / 2

    while k >= 1
      sink(a, k, n)
      k -= 1
    end

    while n > 1
      swap(a, 1, n)
      n -= 1
      sink(a, 1, n)
    end
    a
  end

  def less(pq, i, j)
    pq[i - 1] < pq[j - 1]
  end

  def swap(a, i, j)
    temp = a[i - 1]
    a[i - 1] = a[j - 1]
    a[j - 1] = temp
  end
end

input = ["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]

heap = Heap.new
p heap.sort(input)

When I edit the less and swap methods to address the off by one index in the array it those works correctly on some but not all the elements. If you check the last line is a TEST to run the script but it returns:

["A", "M", "E", "L", "E", "O", "P", "R", "S", "T", "X"]

But the correct answer is

 ["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"] 

Answer 1

The error was coming from the following line:

if !a[j + 1].nil? # check if there is a right child

This line checks if a right node exist. The problem in the heap sort implementation is that we are decreasing n by one in each iteration.

 while n > 1
    swap(a, 1, n)
    n -= 1
    sink(a, 1, n)
 end

Thus we are not keeping track of the elements store in the array that are over index n. Although the array has values stored in the array we are treating only the a[0] to a[n] as a heap.

there for I shouldn't check to see if a[j + 1] is nil rather see if j + 1 is less than or equal to n.

  def sink(a, k, n)
    while 2 * k <= n
      j = 2 * k # child

      if j + 1 <= n # check if there is a right child
        j += 1 if j > 1 && less(a, j, j + 1) # if left child less than right child
      end

      break if !less(a, k, j) # If parent greater than child break
      swap(a, k, j)
      k = j
    end
  end