Ruby Heapify 实施/优化

Question

我正在 Ruby 中实现 Heapify 算法（即将二叉树转换为堆），并认为下面的方法可行。我担心的是我进行了过多的递归调用。

第一次和第二次递归调用是从左右子树中选择最高节点，第三次递归调用是在我交换节点时做同样的事情。没有包括我的 swap_parent_child 方法，有点长但它有效。

def max_heapify(node)
  return nil if node.nil?
  return node if node.left.nil? && node.right.nil?

  left = max_heapify(node.left)
  right = max_heapify(node.right)

  max_value = find_max_value(node, left, right)

  if node.value == max_value
    node
  elsif left && left.value == max_value
    swap_parent_child(node, left)
    max_heapify(node)
    left
  else
    swap_parent_child(node, right)
    max_heapify(node)
    right
  end
end

def find_max_value(node, node2, node3)
  max_value = node.value
  max_value = node2.value if node2 && node2.value > max_value
  max_value = node3.value if node3 && node3.value > max_value

  max_value
end

我已经检查了此处列出的算法，但不确定它是否有效。 https://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html#M502

似乎根据该站点的算法会执行以下操作并停止。

5              5
|\             | \
2 4      =>    10 4
|              |
10             2

我在这里错过了什么？或者堆化一棵树真的需要每个方法调用三个递归调用吗？

Answer 1

对于将来遇到此问题的任何人，正确的方法是堆化表示树的数组，而不是具有父指针和左右指针的实际二叉树。

维基百科上的这个部分对我很有帮助：https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Ruby Heapify 实施/优化

Ruby Heapify Implementation / Optimization

ruby

algorithm

heap

tree

recursion