BST ကို array မသုံးဘဲ Min-Heap အဖြစ်ပြောင်းပါ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Cisco သည် Microsoft က SAP ဓာတ်ခွဲခန်း
Binary Search Tree ဒွိသစ်ပင် သစ်ပင်

ပြProbleနာဖော်ပြချက်

“ BST ကိုခင်းကျင်းခြင်းမရှိဘဲ Min-Heap အဖြစ်ပြောင်းလဲခြင်း” ပြproblemနာကသင့်အား BST (binary search tree) ပေးထားပြီး၎င်းကို min-heap အဖြစ်ပြောင်းလဲရန်လိုအပ်သည်။ min-heap သည် binary search tree ရှိ element အားလုံးပါဝင်သင့်သည်။ အဆိုပါ algorithm ကို linear အချိန်ရှုပ်ထွေးအတွက် run သင့်ပါတယ်။

နမူနာ

input

BST ကို array မသုံးဘဲ Min-Heap အဖြစ်ပြောင်းပါ

output

BST ကို array မသုံးဘဲ Min-Heap အဖြစ်ပြောင်းပါ

BST ကိုခင်းကျင်းခြင်းမရှိဘဲ Min-Heap အဖြစ်ပြောင်းလဲရန်ချဉ်းကပ်မှု

နုံချဉ်းကပ်နည်း

ကျွန်ုပ်တို့သည် BST ကိုခင်းကျင်းခြင်းမရှိဘဲ Min-Heap အဖြစ်ပြောင်းလဲခြင်းသည်ပြweနာကိုဖြေရှင်းနိုင်ပြီး၊ binary ရှာဖွေရေးသစ်ပင်။ In-order ဖြတ်သန်းမှုကိုတွေ့ရှိပြီးတဲ့နောက် min-heap ကိုစတင်ဖွဲ့စည်းလိုက်ပါတယ် (binary tree ဆိုတာကကလေးများအားလုံးသည်မိဘများထက်ပိုငယ်သော subtree ရှိခြင်း) ။ ဒါဆိုကျွန်တော်တို့ min-heap ကိုဘယ်လိုဖန်တီးမလဲ။ ငါတို့ဖန်တီးပါလိမ့်မယ် မိနစ်ပုံ ပြီးပြည့်စုံသော binary tree ပိုင်ဆိုင်မှုကိုသေချာစေမည့် level order traversal တွင် element များကိုနေရာချခြင်းဖြင့်ဖြစ်သည်။ ထို့အပြင်ကျွန်ုပ်တို့အစဉ်အလိုက်ဖြတ်သန်းသွားသောကြောင့် min-heap ၏ပိုင်ဆိုင်မှုသည်ကျေနပ်မှုရှိကြောင်းသေချာသည် (မိဘသည်၎င်း၏ကလေးများထက်ငယ်သည်) ။ သို့သော်ဤသည်ကိုအစဉ်လိုက်ဖြတ်သန်းသိုလှောင်ရန်လိုအပ်သည်။

ထိရောက်သောချဉ်းကပ်မှု

ကျွန်ုပ်တို့၏ binary search tree ကိုပထမ ဦး ဆုံးချိတ်ဆက်ထားသော list တစ်ခုအဖြစ်ပြောင်းလဲလိုက်ပါက O (1) space တွင်ဤပြproblemနာကိုဖြေရှင်းနိုင်သည်။ ချိတ်ဆက်ထားသောစာရင်းတွင်အခြေအနေတစ်ခုစီပါ ၀ င်ရန်လိုအပ်သည်။ ထိုသို့ပြုလုပ်ရန်ကျွန်ုပ်တို့သည်ညာဘက် subtree ကို ဖြတ်၍ ဘယ်ဘက် subtree ကိုဖြတ်သန်းသည်။ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့က node များကို၎င်းရဲ့အစမှာချိတ်ဆက်စာရင်းထဲမှာထည့်လို့ပဲ။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်ချိတ်ဆက်ထားသောစာရင်းအားခွဲခြားထားရန်သေချာသည်။ တစ်ချိန်ကကျွန်ုပ်တို့တွင်အမျိုးအစားခွဲထားသောစာရင်းရှိသည်။ ကျွန်ုပ်တို့၏ပြည့်စုံသော binary tree ပိုင်ဆိုင်မှုကျေနပ်မှုရှိစေရန် node များ၏ဘယ်ဘက်နှင့်ညာဖက်ညွှန်ပြချက်များကိုပြန်လည်စီစဉ်ပေးသည်။ ကျွန်ုပ်တို့သည်နုံချဉ်းကပ်မှုတွင်ပြုလုပ်နေစဉ် min-heap ကိုဖန်တီးရာတွင် level order traversal ကိုအသုံးပြုခဲ့သည်။ ဒီမှာလည်းငါတို့အတူတူသုံးပါလိမ့်မယ်။

ကုဒ်

B ++ ကို BST ကို array ထဲမသုံးဘဲ Min-Heap အဖြစ်ပြောင်းရန် C ++ code

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node* left;
    node* right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// prints the level order traversal of the tree
void levelOrderTraversal(node *root)
{
  if (root == NULL) return;
    queue<node*> q;
    q.push(root);
  while(!q.empty()){
        int qSize = q.size();
        while(qSize--){
            node* nodeAtFront = q.front();
            q.pop();
            if(nodeAtFront->left)
                q.push(nodeAtFront->left);
            if(nodeAtFront->right)
                q.push(nodeAtFront->right);
            cout<<nodeAtFront->data<<" ";
        }
        cout<<endl;
  }
}

void convertBSTToLinkedList(node* root, node* &head_ref)
{
    if(!root)
        return;

  //first convert right subtree into linked list
  convertBSTToLinkedList(root->right, head_ref);
  // insert root into the linked list
  root->right = head_ref;
  //if head pointer exists, then point left pointer to NULL
  if(head_ref)
        head_ref->left = NULL;
    // now head of linked list is current root
    head_ref = root;
    // convert left subtrree recursively
  convertBSTToLinkedList(root->left, head_ref);
}

void convertLinkedListToMinHeap(node* &root, node* head)
{
  // Base Case
  if(!head)
    return;

    //traverse over the linked list in level order traversal fashion
  queue<node*> q;
    //first node of min heap will be smallest element
    //i.e. first element of inorder traversal
    root = head;
    // point head to next node
    head = head->right;
    // left is already null
    root->right = NULL;
    // insert into queue
    q.push(root);
  while(head)
  {
      node* nodeAtFront = q.front();
      q.pop();
      // now remove one node from linked list and make left child
      // if there are more nodes make a right child
      // push them into queue
      node* leftNode = head;
      head = head->right;
      leftNode->right = NULL;
      nodeAtFront->left = leftNode;
      q.push(leftNode);
      // similarly do the same for right child if it exists
      if(head){
            node* rightNode = head;
            head = head->right;
            rightNode->right = NULL;
            nodeAtFront->right = rightNode;
            q.push(rightNode);
      }
  }
}

// Function to convert BST into a Min-Heap
// without using any extra space
node* BSTToMinHeap(node* &root)
{
  // head of Linked List
  node *head = NULL;
  // get converted linked list
  convertBSTToLinkedList(root, head);
  // now set the root for min heap
  root = NULL;
  // convert the linked list into min heap
  convertLinkedListToMinHeap(root, head);
}

int main()
{

  node* root = create(5);
  root->left = create(4);
  root->right = create(6);
  root->left->left = create(2);
  root->left->right = create(3);

  BSTToMinHeap(root);

        levelOrderTraversal(root);

  return 0;
}
2
4 3
5 6

BST ကိုခင်းကျင်းခြင်းမရှိဘဲ Min-Heap အဖြစ်ပြောင်းလဲရန် Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }
 
  static void levelOrderTraversal(node root)
  {
    if (root == null) return;
      Queue<node> q = new LinkedList<>();
      q.add(root);
    while(!q.isEmpty()){
          int qSize = q.size();
          while(qSize-- > 0){
              node nodeAtFront = q.peek();
              q.remove();
              if(nodeAtFront.left != null)
                  q.add(nodeAtFront.left);
              if(nodeAtFront.right != null)
                  q.add(nodeAtFront.right);
              System.out.print(nodeAtFront.data+" ");
          }
          System.out.println();
    }
  }
  
  static node convertBSTToLinkedList(node root, node head_ref)
  {
      if(root == null)
          return head_ref;
  
    //first convert right subtree into linked list
    head_ref = convertBSTToLinkedList(root.right, head_ref);
    // insert root into the linked list
    root.right = head_ref;
    //if head pointer exists, then point left pointer to NULL
    if(head_ref != null)
          head_ref.left = null;
      // now head of linked list is current root
      head_ref = root;
      // convert left subtrree recursively
    head_ref = convertBSTToLinkedList(root.left, head_ref);
    
    return head_ref;
  }
  
  static node convertLinkedListToMinHeap(node root, node head)
  {
    // Base Case
    if(head == null)
      return null;
  
      //traverse over the linked list in level order traversal fashion
    Queue<node> q = new LinkedList<>();
      //first node of min heap will be smallest element
      //i.e. first element of inorder traversal
      root = head;
      // point head to next node
      head = head.right;
      // left is already null
      root.right = null;
      // insert into queue
      q.add(root);
    while(head != null)
    {
        node nodeAtFront = q.peek();
        q.remove();
        // now remove one node from linked list and make left child
        // if there are more nodes make a right child
        // push them into queue
        node leftNode = head;
        head = head.right;
        leftNode.right = null;
        nodeAtFront.left = leftNode;
        q.add(leftNode);
        // similarly do the same for right child if it exists
        if(head != null){
              node rightNode = head;
              head = head.right;
              rightNode.right = null;
              nodeAtFront.right = rightNode;
              q.add(rightNode);
        }
    }
    return root;
  }
  
  // Function to convert BST into a Min-Heap
  // without using any extra space
  static node BSTToMinHeap(node root)
  {
    // head of Linked List
    node head = null;
    // get converted linked list
    head = convertBSTToLinkedList(root, head);
    // now set the root for min heap
    root = null;
    // convert the linked list into min heap
    root = convertLinkedListToMinHeap(root, head);
    return root;
  }
  
  public static void main(String[] args)
  {
  
    node root = create(5);
    root.left = create(4);
    root.right = create(6);
    root.left.left = create(2);
    root.left.right = create(3);
  
    root = BSTToMinHeap(root);
  
      levelOrderTraversal(root);
  }

}
2 
4 3 
5 6 

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်ပထမဆုံးသစ်ပင်ကိုချိတ်ဆက်ထားသောစာရင်းတစ်ခုအဖြစ်ပြောင်းလဲခဲ့ပြီး၊ နှစ် ဦး စလုံး liner အချိန်ရှုပ်ထွေးစစ်ဆင်ရေးဖြစ်သော PF ။ ထို့ကြောင့် linear အချိန်ရှုပ်ထွေးအောင်မြင်သည်။

အာကာသရှုပ်ထွေးမှု

အို (မှတ်တမ်း N)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ကကလေးတွေကိုအဆင့်တစ်ခုတည်းမှာသိုလှောင်ဖို့တန်းစီလိုက်တာလေ။ ဤသည်လော်ဂရစ်သမ်အာကာသရှုပ်ထွေးကြာပါသည်။ ဒါပေမယ့် algorithm ကိုသူ့ဟာသူအရပျ၌အလုပ်ဖြစ်တယ်။