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

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。
                        
                        5年前关闭。
                                                                                            
                
        
我被要求将递归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);
    }