11

これは、私が最近遭遇したインタビューの質問の 1 つです。

完全またはほぼ完全なバイナリ ツリーのルート アドレスが与えられた場合、ツリーを最大ヒープに変換する関数を作成する必要があります。

ここには配列は含まれていません。ツリーはすでに構築されています。

たとえば、

              1   
         /         \
        2           5
      /   \       /   \ 
     3      4    6     7

出力として可能な最大ヒープのいずれかを持つことができます--

              7   
         /         \
        3           6
      /   \       /   \ 
     2     1     4     5

また

              7   
         /         \
        4           6
      /   \       /   \ 
     2     3     1     5

等...

私は解決策を書きましたが、前後のトラバーサルの組み合わせを使用しましたが、それは O(n^2) で実行されると思います。私のコードは次の出力を提供します。

              7   
         /         \
        3           6
      /   \       /   \ 
     1     2     4     5

私はより良い解決策を探していました。誰か助けてくれませんか？

編集 ：

マイコード

void preorder(struct node* root)
{    
    if(root==NULL)return;
    max_heapify(root,NULL);
    preorder(root->left); 
    preorder(root->right);
}
void max_heapify(struct node* root,struct node* prev)
{
    if(root==NULL)
        return ;             
    max_heapify(root->left,root);
    max_heapify(root->right,root);
    if(prev!=NULL && root->data > prev->data)
    {
        swapper(root,prev);
    }     
}
void swapper(struct node* node1, struct node* node2)
{   
    int temp= node1->data;
    node1->data = node2->data;
    node2->data = temp;
}
4

4 に答える 4

6

以下の手順でO(NlogN)時間でできると思います。 http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html

左と右の両方のサブツリーがヒープである要素がツリーにあるとします。

          E
       H1   H2

E、H1、および H2 によって形成されるこの Tree は、要素 E を正しい位置まで泳がせることにより、logN 時間でヒープ化できます。

したがって、ヒープの構築をボトムアップで開始します。一番左のサブツリーに移動し、単純な比較によってヒープに変換します。兄弟のためにもこれを行います。次に、上に移動してヒープに変換します。

同様に、すべての要素に対してこれを行います。

編集: コメントで述べたように、複雑さは実際には O(N) です。

于 2014-07-17T11:39:01.653 に答える
2

親ノードに簡単にアクセスできない場合や配列表現がない場合、ツリーをたどって配列に参照を記録できる場合（O（N））、方法がわかりません。

        1   
     /    \
    2       5
  /   \    / \ 
 3     4  6   7

from the last parent node to the root node(in your case 5,2,1:
  for each node make it compare to their children:
    if children is larger than parent, swap parent and children:
      if swapped: then check the new children's childrens utill no swap

        1   
     /    \
    2       7
  /   \    / \ 
 3     4  6   5    check [7]   5<-->7

        1   
     /    \
    4       7
  /   \    / \ 
 3     2  6   5    check [2]   4<-->2

        7   
     /    \
    4       1
  /   \    / \ 
 3     2  6   5    check [1]   7<-->1

        7   
     /    \
    4       6
  /   \    / \ 
 3     2  1   5    check [1]   6<-->1

それだ！複雑さは O(N*LogN) である必要があります。

于 2014-07-17T11:54:34.060 に答える
0

postOrderTraverse を修正するだけで 1 つの作品が得られると思います。これは O(n)

void Heapify_Min(TreeNode* node)
{
  if(! = node) return;
   Heapify_Min(node->left);
   Heapify_Min(node->right);
   TreeNode* largest = node;
   if(node->left && node->left->val > node->val)
      largest = node->left;
   if(node->right && node->right->val > node->val)
      largest = node->right;

  if(largest != node)
  {
    swap(node, largest)
  }
}

void swap(TreeNode* n1, TreeNode* n2)
{
    TreeNode* temp = n1->left;
    n1->left = n2->left;
    n2->left =temp;

    temp = n1->right;
    n1->right = n2->right;
    n2->right = temp;
}

}
于 2015-01-14T06:48:54.247 に答える