Max-Heapify Binary Tree

Это один из вопросов, которые я недавно встретил.

Учитывая корневой адрес полного или почти полного бинарного дерева, мы должны написать функцию для преобразования дерева в макс-кучу.

Здесь нет массивов. Дерево уже построено.

Например,

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

может иметь любую возможную максимальную кучу в качестве выхода -

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

или

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

и т.д...

Я написал решение, но использовал комбинацию pre и post traversals, но, думаю, работает в 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;
}

Ответ 1

Я думаю, что это можно сделать в O (NlogN) раз в следующей процедуре. http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html

Предположим, что в дереве есть элемент, у которого оба левого и правого поддеревьев являются кучами.

          E
       H1   H2

Это дерево, образованное E, H1 и H2, может быть разрушено в logN-времени, заставив элемент E плавать до его правильного положения.

Следовательно, мы начинаем строить кучу снизу вверх. Перейти к самому левому поддереву и преобразовать его в кучу путем тривиального сравнения. Сделайте это и для этого брата. Затем поднимитесь и преобразуйте его в кучу.

Подобным образом сделайте это для каждого элемента.

EDIT: Как упоминалось в комментариях, сложность на самом деле O (N).

Ответ 2

Я не знаю, каким образом, если вы не можете получить доступ к родительскому node легкому или отсутствующему представлению массива, если бы вы могли пересечь дерево, чтобы записать его ref в массив (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 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).

Ответ 3

Я думаю, вы можете получить одну работу, просто пересмотрев postOrderTraverse. Это 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;
}

}