ReheapUp和ReheapDown递归到迭代转换C＃

我被要求将递归ReheapUp和ReheapDown算法转换为另一种迭代形式。下面是递归版本的伪代码：ReheapUp和ReheapDown递归到迭代转换C＃

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

请告诉我，我在做什么错。

来源

2014-10-05 TheAuzzieJesus

请告诉我你的想法是错误的。 – paqogomez 2014-10-05 04:31:39

@paqogomez我写的迭代代码不正确。当输入样本数据时，结果不会正确重新排列。 – TheAuzzieJesus 2014-10-05 04:40:58

请添加样本输入，期望输出和实际输出。 – paqogomez 2014-10-05 04:41:43

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

来源

2014-10-05 05:32:02 SuperDicko

ReheapUp和ReheapDown递归到迭代转换C＃

回答

相关问题