Ruby Heapsort: `sink': nil:NilClass 的未定义方法 `>'

Question

我目前正在写 Robert Sedgewicks Algorithm's 这本书。我正在尝试实现堆排序，但遇到错误

'sink': undefined method >' for nil: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] 开始，但我有点不清楚在 sort 方法中是如何完成的Java 实施。我也有点奇怪，该方法需要传递一个从索引 1 开始的数组。所以我的理解是 Java 实现中的 sort 方法会设置数组。

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

Ruby sort 在 Ruby 中的 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 方法以通过数组中的一个索引解决关闭问题时，这些方法在某些但不是所有元素上都能正常工作。如果您检查最后一行是运行脚本的测试，但它 returns:

["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

Ruby Heapsort: `sink': nil:NilClass 的未定义方法 `>'

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

ruby

algorithm

heapsort