Max heap to min heap conversion

Given a array of integers, which is form of binary max heap. Our goal is to transform this max into a min heap in efficient way. For example.

convert max heap to min heap

In above image clear indicates swapping the node value. Note that there is possible you are logic are based on different calculation. But converted resultant tree should be form of min heap. (conclusion resultantant tree can be more than one form are possible but those will follow the min heap properties).

Here given code implementation process.

//C Program
//Max heap to min heap conversion
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
  int auxiliary=arr[first];
  arr[first]=arr[second];
  arr[second]=auxiliary;
}
//Compare the properties of min heap
int compare(int arr[],int left,int right,int root,int size)
{
  int location = -1;

  if(left < size &&  arr[left] < arr[root] )
  {

    if(right < size && arr[right] < arr[left])
    {
      swap(arr,right,root);
      location = right;
    }
    else
    {
      swap(arr,left,root);
      location = left;
    }
  }
  else if(right < size && arr[right] < arr[root])
  {
    swap(arr,right,root);
    location = right;
  }
  return location;
}
void heap(int arr[],int size,int root)
{
  int left  = 2*root+1;
  int right = 2*root+2;
 
  int next_in = compare(arr, left, right, root, size);
 
  if(next_in != -1)
  {
    heap(arr,size,next_in);
  }
}
//Display array elements
void print_data(int arr[],int size)
{
  
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
  printf("\n");
}

void min_heap(int arr[],int size)
{
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
}
int main()
{

  /*
         10
       /    \
      9       8
     / \     / \
    5   7   1   6
   /
  4
  */
  //Collection of max heap elements
  int heap[] = { 10,  9,  8,  5,  7,  1,  6, 4}; 

  //Get the size of elements
  int n = sizeof(heap) / sizeof(heap[0]); 

  printf("  Max heap : \n");
  print_data(heap,n);
  /*
         1
       /    \
      4       6
     / \     / \
    5   7   8   10
   /
  9
  */
  min_heap(heap,n);
  printf("  Min heap : \n");
  print_data(heap,n);
  return 0;
}

Output

  Max heap :
 10  9  8  5  7  1  6  4
  Min heap :
  1  4  6  5  7  8 10  9
/*
  C++ Program
  Max heap to min heap conversion
*/
#include<iostream>
using namespace std;

class MyHeap {
  public:

    //Swap two element in array
    void swap(int arr[], int first, int second) {
      int auxiliary = arr[first];
      arr[first] = arr[second];
      arr[second] = auxiliary;
    }
  //Compare the properties of min heap
  int compare(int arr[], int left, int right, int root, int size) {
    int location = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        this->swap(arr, right, root);
        location = right;
      } else {
        this->swap(arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      this->swap(arr, right, root);
      location = right;
    }
    return location;
  }
  void heap(int arr[], int size, int root) {
    int left = 2 *root + 1;
    int right = 2 *root + 2;
    int next_in = this->compare(arr, left, right, root, size);
    if (next_in != -1) {
      this->heap(arr, size, next_in);
    }
  }
  //Display array elements
  void print_data(int arr[], int size) {
    for (int i = 0; i < size; i++) {
      cout << " " << arr[i];
    }
    cout << "\n";
  }
  void min_heap(int arr[], int size) {
    for (int i = (size / 2) - 1; i >= 0; i--) {
      this->heap(arr, size, i);
    }
  }
};
int main() {
  MyHeap obj = MyHeap();
  /*
             10
           /    \
          9       8
         / \     / \
        5   7   1   6
       /
      4
      */
  //Collection of max heap elements
  int heap_data[] = {
    10,
    9,
    8,
    5,
    7,
    1,
    6,
    4
  };
  //Get the size of elements
  int n = sizeof(heap_data) / sizeof(heap_data[0]);
  cout << " Max heap : \n";
  obj.print_data(heap_data, n);
  /*
             1
           /    \
          4       6
         / \     / \
        5   7   8   10
       /
      9
      */
  obj.min_heap(heap_data, n);
  cout << " Min heap : \n";
  obj.print_data(heap_data, n);
  return 0;
}

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
/*
  Java Program
  Max heap to min heap conversion
*/
public class MyHeap {
  
  //Swap two element in array
  public void swap(int []arr,int first,int second)
  {
    int auxiliary=arr[first];
    arr[first]=arr[second];
    arr[second]=auxiliary;
  }

  //Compare the properties of min heap
  public int compare(int []arr,int left,int right,int root,int size)
  {
    int location = -1;

    if(left < size &&  arr[left] < arr[root] )
    {

      if(right < size && arr[right] < arr[left])
      {
        swap(arr,right,root);
        location = right;
      }
      else
      {
        swap(arr,left,root);
        location = left;
      }
    }
    else if(right < size && arr[right] < arr[root])
    {
      swap(arr,right,root);
      location = right;
    }
    return location;
  }
  public void heap(int []arr,int size,int root)
  {
    int left  = 2*root+1;
    int right = 2*root+2;
   
    int next_in = compare(arr, left, right, root, size);
   
    if(next_in != -1)
    {
      heap(arr,size,next_in);
    }
  }
  //Display array elements
  public void print_data(int []arr,int size)
  {
    
    for(int i = 0; i < size; i++)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }

  public void min_heap(int []arr,int size)
  {
    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap(arr,size,i);
    }
  }
  
  public static void main(String[] args) {
    
    MyHeap obj = new MyHeap();
      
    /*
           10
         /    \
        9       8
       / \     / \
      5   7   1   6
     /
    4
    */
    //Collection of max heap elements
    int heap_data[] = { 10,  9,  8,  5,  7,  1,  6, 4};  
    
    //Get the size of elements
    int n = heap_data.length; 

    System.out.print("  Max heap : \n");
    obj.print_data(heap_data,n);
    /*
           1
         /    \
        4       6
       / \     / \
      5   7   8   10
     /
    9
    */
    obj.min_heap(heap_data,n);
    System.out.print("  Min heap : \n");
    obj.print_data(heap_data,n);

  } 
}

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
/*
  C# Program
  Max heap to min heap conversion
*/
using System;

public class MyHeap {
  //Swap two element in array
  public void swap(int[] arr, int first, int second) {
    int auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  //Compare the properties of min heap
  public int compare(int[] arr, int left, int right, int root, int size) {
    int location = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        swap(arr, right, root);
        location = right;
      } else {
        swap(arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      swap(arr, right, root);
      location = right;
    }
    return location;
  }
  public void heap(int[] arr, int size, int root) {
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int next_in = compare(arr, left, right, root, size);
    if (next_in != -1) {
      heap(arr, size, next_in);
    }
  }
  //Display array elements
  public void print_data(int[] arr, int size) {
    for (int i = 0; i < size; i++) {
      Console.Write(" " + arr[i]);
    }
    Console.Write("\n");
  }
  public void min_heap(int[] arr, int size) {
    for (int i = (size / 2) - 1; i >= 0; i--) {
      heap(arr, size, i);
    }
  }
  public static void Main(String[] args) {
    MyHeap obj = new MyHeap();
    /*
               10
             /    \
            9       8
           / \     / \
          5   7   1   6
         /
        4
        */
    //Collection of max heap elements
    int []heap_data = {
      10,
      9,
      8,
      5,
      7,
      1,
      6,
      4
    };
    //Get the size of elements
    int n = heap_data.Length;
    Console.Write(" Max heap : \n");
    obj.print_data(heap_data, n);
    obj.min_heap(heap_data, n);
    Console.Write(" Min heap : \n");
    obj.print_data(heap_data, n);
  }
}

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
<?php
/*
  Php Program
  Max heap to min heap conversion
*/
class MyHeap {
  //Swap two element in array

  public  function swap(&$arr, $first, $second) {
    $auxiliary = $arr[$first];
    $arr[$first] = $arr[$second];
    $arr[$second] = $auxiliary;
  }
  //Compare the properties of min heap

  public  function compare(&$arr, $left, $right, $root, $size) {
    $location = -1;
    if ($left < $size && $arr[$left] < $arr[$root]) {
      if ($right < $size && $arr[$right] < $arr[$left]) {
        $this->swap($arr, $right, $root);
        $location = $right;
      } else {
        $this->swap($arr, $left, $root);
        $location = $left;
      }
    } else
    if ($right < $size && $arr[$right] < $arr[$root]) {
      $this->swap($arr, $right, $root);
      $location = $right;
    }
    return $location;
  }
  public  function heap(&$arr, $size, $root) {
    $left = 2 *$root + 1;
    $right = 2 *$root + 2;
    $next_in = $this->compare($arr, $left, $right, $root, $size);
    if ($next_in != -1) {
      $this->heap($arr, $size, $next_in);
    }
  }
  //Display array elements

  public  function print_data($arr, $size) {
    for ($i = 0; $i < $size; $i++) {
      echo(" ". $arr[$i]);
    }
    echo("\n");
  }
  public  function min_heap(&$arr, $size) {
    for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
      $this->heap($arr, $size, $i);
    }
  }
}

function main() {
  $obj = new MyHeap();
  /*
             10
           /    \
          9       8
         / \     / \
        5   7   1   6
       /
      4
      */
  //Collection of max heap elements
  $heap_data = array(10, 9, 8, 5, 7, 1, 6, 4);
  //Get the size of elements
  $n = count($heap_data);
  echo(" Max heap : \n");
  $obj->print_data($heap_data, $n);
  /*
             1
           /    \
          4       6
         / \     / \
        5   7   8   10
       /
      9
      */

  $obj->min_heap($heap_data, $n);
  echo(" Min heap : \n");
  $obj->print_data($heap_data, $n);

}
main();

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
/*
  Node Js Program
  Max heap to min heap conversion
*/
class MyHeap {
  //Swap two element in array
  swap(arr, first, second) {
    var auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }

  //Compare the properties of min heap
  compare(arr, left, right, root, size) {
    var location = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        this.swap(arr, right, root);
        location = right;
      } else {
        this.swap(arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      this.swap(arr, right, root);
      location = right;
    }

    return location;
  }
  heap(arr, size, root) {
    var left = 2 *root + 1;
    var right = 2 *root + 2;
    var next_in = this.compare(arr, left, right, root, size);
    if (next_in != -1) {
      this.heap(arr, size, next_in);
    }
  }

  //Display array elements
  print_data(arr, size) {
    for (var i = 0; i < size; i++) {
      process.stdout.write(" " + arr[i]);
    }

    process.stdout.write("\n");
  }
  min_heap(arr, size) {
    for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
      this.heap(arr, size, i);
    }
  }
}

function main(args) {
  var obj = new MyHeap();
  /*
             10
           /    \
          9       8
         / \     / \
        5   7   1   6
       /
      4
      */
  //Collection of max heap elements
  var heap_data = [10, 9, 8, 5, 7, 1, 6, 4];
  //Get the size of elements
  var n = heap_data.length;
  process.stdout.write(" Max heap : \n");
  obj.print_data(heap_data, n);
  /*
             1
           /    \
          4       6
         / \     / \
        5   7   8   10
       /
      9
      */
  obj.min_heap(heap_data, n);
  process.stdout.write(" Min heap : \n");
  obj.print_data(heap_data, n);
}

main();

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
#  Python 3 Program
#  Max heap to min heap conversion

class MyHeap :
  # Swap two element in array
  def swap(self, arr, first, second) :
    auxiliary = arr[first]
    arr[first] = arr[second]
    arr[second] = auxiliary
   # Compare the properties of min heap
  def compare(self, arr, left, right, root, size) :
    location = -1
    if (left < size and arr[left] < arr[root]) :
      if (right < size and arr[right] < arr[left]) :
        self.swap(arr, right, root)
        location = right
      else :
        self.swap(arr, left, root)
        location = left
      
    elif (right < size and arr[right] < arr[root]) :
      self.swap(arr, right, root)
      location = right
    
    return location
  
  def heap(self, arr, size, root) :
    left = 2 * root + 1
    right = 2 * root + 2
    next_in = self.compare(arr, left, right, root, size)
    if (next_in != -1) :
      self.heap(arr, size, next_in)
    
   # Display array elements
  def print_data(self, arr, size) :
    i = 0
    while (i < size) :
      print(" ", arr[i], end = "")
      i += 1
    
    print("\n", end = "")
  
  def min_heap(self, arr, size) :
    i = (int(size / 2)) - 1
    while (i >= 0) :
      self.heap(arr, size, i)
      i -= 1
    
  

def main() :
  obj = MyHeap() # Collection of max heap elements
  #
  #             10
  #           /    \
  #          9       8
  #         / \     / \
  #        5   7   1   6
  #       /
  #      4
  #      
  
  # Collection of max heap elements

  heap_data = [10, 9, 8, 5, 7, 1, 6, 4] # Get the size of elements
  n = len(heap_data)
  print(" Max heap : \n", end = "")
  obj.print_data(heap_data, n)
  #
  #             1
  #           /    \
  #          4       6
  #         / \     / \
  #        5   7   8   10
  #       /
  #      9
  #      
  
  obj.min_heap(heap_data, n)
  print(" Min heap : \n", end = "")
  obj.print_data(heap_data, n)


if __name__ == "__main__":
  main()

Output

 Max heap :
  10  9  8  5  7  1  6  4
 Min heap :
  1  4  6  5  7  8  10  9
#  Ruby Program
#  Max heap to min heap conversion

class MyHeap 
   # Swap two element in array
  def swap(arr, first, second) 
    auxiliary = arr[first]
    arr[first] = arr[second]
    arr[second] = auxiliary
  end
   # Compare the properties of min heap
  def compare(arr, left, right, root, size) 
    location = -1
    if (left < size && arr[left] < arr[root]) 
      if (right < size && arr[right] < arr[left]) 
        self.swap(arr, right, root)
        location = right
      else 
        self.swap(arr, left, root)
        location = left
      end
    elsif (right < size && arr[right] < arr[root]) 
      self.swap(arr, right, root)
      location = right
    end
    return location
  end
  def heap(arr, size, root) 
    left = 2 * root + 1
    right = 2 * root + 2
    next_in = self.compare(arr, left, right, root, size)
    if (next_in != -1) 
      self.heap(arr, size, next_in)
    end
  end
   # Display array elements
  def print_data(arr, size) 
    i = 0
    while (i < size) 
      print(" ", arr[i])
      i += 1
    end
    print("\n")
  end
  def min_heap(arr, size) 
    i = (size / 2) - 1
    while (i >= 0) 
      self.heap(arr, size, i)
      i -= 1
    end
  end
end
def main() 
  obj = MyHeap.new()
  #
  #             10
  #           /    \
  #          9       8
  #         / \     / \
  #        5   7   1   6
  #       /
  #      4
  #      
  
   # Collection of max heap elements
  heap_data = [10, 9, 8, 5, 7, 1, 6, 4]
   # Get the size of elements
  n = heap_data.length
  print(" Max heap  :\n")
  obj.print_data(heap_data, n)
  #
  #             1
  #           /    \
  #          4       6
  #         / \     / \
  #        5   7   8   10
  #       /
  #      9
  #      
  
  obj.min_heap(heap_data, n)
  print(" Min heap  :\n")
  obj.print_data(heap_data, n)
end
main()

Output

 Max heap  :
 10 9 8 5 7 1 6 4
 Min heap  :
 1 4 6 5 7 8 10 9
/*
  Scala Program
  Max heap to min heap conversion
*/
class MyHeap {
  //Swap two element in array
  def swap(arr: Array[Int], first: Int, second: Int): Unit = {
    val auxiliary: Int = arr(first);
    arr(first) = arr(second);
    arr(second) = auxiliary;
  }
  //Compare the properties of min heap
  def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
    var location: Int = -1;

    if (left < size && arr(left) < arr(root)) {
      if (right < size && arr(right) < arr(left)) {
        this.swap(arr, right, root);
        location = right;
      } else {
        this.swap(arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr(right) < arr(root)) {
      this.swap(arr, right, root);
      location = right;
    }
    return location;
  }
  def heap(arr: Array[Int], size: Int, root: Int): Unit = {
    val left: Int = 2 * root + 1;
    val right: Int = 2 * root + 2;
    val next_in: Int = this.compare(arr, left, right, root, size);

    if (next_in != -1) {
      this.heap(arr, size, next_in);
    }
  }
  //Display array elements
  def print_data(arr: Array[Int], size: Int): Unit = {
    var i: Int = 0;
    while (i < size) {
      print(" " + arr(i));
      i += 1;
    }
    print("\n");
  }
  def min_heap(arr: Array[Int], size: Int): Unit = {
    var i: Int = ((size / 2).toInt) - 1;
    while (i >= 0) {
      this.heap(arr, size, i);
      i -= 1;
    }
  }
}
object Main {
  def main(args: Array[String]): Unit = {
    val obj: MyHeap = new MyHeap();

    /*
                 10
               /    \
              9       8
             / \     / \
            5   7   1   6
           /
          4
          */
    //Collection of max heap elements
    var heap_data: Array[Int] = Array(10, 9, 8, 5, 7, 1, 6, 4);

    //Get the size of elements
    val n: Int = heap_data.length;
    print(" Max heap : \n");
    obj.print_data(heap_data, n);

    /*
                 1
               /    \
              4       6
             / \     / \
            5   7   8   10
           /
          9
          */
    obj.min_heap(heap_data, n);
    print(" Min heap : \n");
    obj.print_data(heap_data, n);
  }
}

Output

 Max heap :
 10 9 8 5 7 1 6 4
 Min heap :
 1 4 6 5 7 8 10 9
/*
  Swift Program
  Max heap to min heap conversion
*/
class MyHeap {
  //Swap two element in array
  func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
    let auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  //Compare the properties of min heap
  func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
    var location = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        self.swap(&arr, right, root);
        location = right;
      } else {
        self.swap(&arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      self.swap(&arr, right, root);
      location = right;
    }
    return location;
  }
  func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
    let left = 2 * root + 1;
    let right = 2 * root + 2;
    let next_in = self.compare(&arr, left, right, root, size);
    if (next_in != -1) {
      self.heap(&arr, size, next_in);
    }
  }
  //Display array elements
  func print_data(_ arr:  [Int], _ size: Int) {
    var i = 0;
    while (i < size) {
      print(" ", arr[i], terminator: "");
      i += 1;
    }
    print("\n", terminator: "");
  }
  func min_heap(_ arr: inout [Int], _ size: Int) {
    var i = (size / 2) - 1;
    while (i >= 0) {
      self.heap(&arr, size, i);
      i -= 1;
    }
  }
}
func main() {
  let obj = MyHeap();
  /*
               10
             /    \
            9       8
           / \     / \
          5   7   1   6
         /
        4
        */
  //Collection of max heap elements
  var heap_data = [10, 9, 8, 5, 7, 1, 6, 4];
  //Get the size of elements
  let n = heap_data.count;
  print(" Max heap : \n", terminator: "");
  obj.print_data(heap_data, n);
  /*
               1
             /    \
            4       6
           / \     / \
          5   7   8   10
         /
        9
        */
  obj.min_heap(&heap_data, n);
  print(" Min heap : \n", terminator: "");
  obj.print_data(heap_data, n);
}
main();

Output

 Max heap :
  10  9  8  5  7  1  6  4
 Min heap :
  1  4  6  5  7  8  10  9

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved