RubyHeap排序：“接收器”：用于nil:NilClass的未定义方法`>‘

Question

我目前正在写罗伯特·塞奇威克斯算法的书。我正在尝试实现堆排序，但是我遇到了一个错误

“接收器”：未定义的方法>为0:NilClass的方法

发生此错误的原因是，当数组传递给sort方法时，它在0索引处有11个元素。当它将索引n (数组中的元素数)与1交换时，它将nil与字符串进行比较。这意味着n为11，但没有11索引，因为数组索引从0开始。

以下是本书中堆排序方法的Java实现：

 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);
     }
}

下面是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

现在，在这本书中，数组忽略了a[0]的位置，从a[1]开始，但我有点不清楚是如何在Java实现中的sort方法中这样做的。对于我来说，这个方法需要传递一个从索引1开始的数组，这也有点奇怪。因此，我的理解是，sort实现中的方法将设置数组。

​

​

注意，在示例中，数组中的第一个元素是如何从索引1 a[1]开始的。这是在sort方法中完成的吗？这意味着重新排列数组以从索引1开始？

Ruby中sort的Ruby实现正确吗？还是有错误？

堆排序的完全实现。

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)

当我编辑less和swap方法以通过数组中的一个索引来处理off时，这些方法正确地工作在某些元素上，而不是所有元素上。如果您检查最后一行是运行脚本的测试，但它返回：

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

但正确的答案是

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

Answer 1

错误来自以下行：

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

此行检查是否存在正确的节点。堆排序实现中的问题是，在每次迭代中我们都要减少一个n。

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

因此，我们没有跟踪数组中存储在索引n上的元素。尽管数组中存储了值，但我们只将a[0]到a[n]视为堆。

​

因为我不应该检查a[j + 1]是否为零，而是查看j + 1是否小于或等于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