c# - ReheapUp 和 ReheapDown 递归到迭代的转换 C#

标签 c# recursion heap binary-tree iteration

<分区>

有人要求我将递归 ReheapUp 和 ReheapDown 算法转换为替代迭代形式。这是递归版本的伪代码:

ReheapUp(node)
begin
   if NOT node = 0
       parent ← (node - 1) / 2 // integer division
       if heap[node] > heap[parent]
           Swap(heap[parent], heap[node])
           ReheapUp(parent)
       end-if
   end-if
end

ReheapDown(node)
begin
   leftChild ← node * 2 + 1
   rightChild ← node * 2 + 2
   if leftChild <= lastUsed
       largest ← leftChild
       if rightChild <= lastUsed AND array[largest] < array[rightChild]
           largest ← rightChild
       end-if
       if array[node] < array[largest]
           Swap(array[node], array[largest])
           ReheapDown(largest)
       end-if
   end-if
end

这是我的尝试:

private void ReheapUp(int index)
{
   bool Terminate;
   int Processing = index;

   do
   {
       Terminate = true;

       if (Processing != 0)
       {
           int Parent = PARENT(Processing);

           if (_Data[Processing].CompareTo(_Data[Parent]) > 0)
           {
               Utility.Swap(ref _Data[Parent], ref _Data[Processing]);
               Terminate = false;
               Processing = Parent;
           }
       }
   } while (!Terminate);
}

private void ReheapDown(int index)
{
   bool Terminate;

   int Processing = index,
       Largest = -1;

   do
   {
       Terminate = true;
       int LeftChild = CLEFT(Processing),
           RightChild = CRIGHT(Processing);

       if (LeftChild <= _LastUsed)
       {
           Largest = LeftChild;

           if (RightChild <= _LastUsed && _Data[Largest].CompareTo(_Data[RightChild]) < 0)
               Largest = RightChild;

           if (_Data[index].CompareTo(_Data[Largest]) < 0)
           {
               Utility.Swap(ref _Data[Processing], ref _Data[Largest]);
               Terminate = false;
               Processing = Largest;
           }
       }
   } while (!Terminate);
}

请告诉我我做错了什么。

最佳答案

您的 ReheapDown 方法有一个小问题。这应该有效:

    private void ReheapDown(int index)
    {
        bool Terminate;

        int Processing = index,
            Largest = -1;

        do
        {
            Terminate = true;
            int LeftChild = CLEFT(Processing),
                RightChild = CRIGHT(Processing);

            if (LeftChild <= _LastUsed)
            {
                Largest = LeftChild;

                if (RightChild <= _LastUsed && _Data[Largest].CompareTo(_Data[RightChild]) < 0)
                    Largest = RightChild;

                if (_Data[Processing].CompareTo(_Data[Largest]) < 0)
                {
                    Utility.Swap(ref _Data[Processing], ref _Data[Largest]);
                    Terminate = false;
                    Processing = Largest;
                }
            }
        } while (!Terminate);
    }

关于c# - ReheapUp 和 ReheapDown 递归到迭代的转换 C#，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26199570/

上一篇：c# - 为什么这个 block 读取代码不起作用？

下一篇：c# - Windows 8.1 应用程序中的 FlipView 渲染问题

相关文章：

c# - 从 C# 传递 SSIS 参数

c++ - 概率计算器中的段错误

c++ - 二叉堆无匹配函数错误

arrays - 有效合并多集的 n 个元素的数据结构

algorithm - 最小化连接成本的解决方案的复杂性分析

c# - BitArray 改变范围内的位

c# - 是否可以在后台运行 aspx 文件作为 "In memory"操作

c# - 如何使用 Mongodb C# 驱动程序进行谓词搜索

python从递归方法返回列表

arrays - 如何在 Ruby 中递归查找二维数组的排列