Implement min heap using array

Here given code implementation process.

//C Program
//Implement min heap using array
#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;
}

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_step = compare(arr, left, right, root, size);
 
  if(next_step != -1)
  {
    heap(arr,size,next_step);
  }
}
//Show array elements
void print_data(int arr[],int size)
{
  printf("\n");
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
}
void min_heap(int arr[],int size)
{
  
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
}
 int main()

 {
  //Array elements
  int arr[] = {4, 7, 8, 2, 9, 3, 1, 6, 10};

    /*

    initial elements

              4
           /      \
          /        \
         7          8
       /   \       /  \
      2     9     3    1
     / \   
    6   10 
  */
  //find the length of array elements
  int size = sizeof(arr)/sizeof(arr[0]);

  printf("\n Before elements ");
  //Display array elements
  print_data(arr,size);


  min_heap(arr,size);

  /*
    After convert into min heap elements

              1
           /      \
          /        \
         2          3
       /   \       /  \
      6     9     4    8
     / \   
    7   10 
  */

  printf("\n After Min heap elements ");
  //Display array elements
  print_data(arr,size);

  printf("\n");
  return 0;
}

Output

  Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
/*
 C++ Program
 Implement min heap using array
*/

#include<iostream>

using namespace std;
class minHeap {
  public:
    void swap(int arr[], int first, int second) {
      int auxiliary = arr[first];
      arr[first] = arr[second];
      arr[second] = auxiliary;
    }
  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_step = this->compare(arr, left, right, root, size);
    if (next_step != -1) {
      this->heap(arr, size, next_step);
    }
  }
  void print_data(int arr[], int size) {
    cout << "\n";
    int i = 0;
    while (i < size) {
      cout << "   " << arr[i];
      i++;
    }
  }
  void min_heap(int arr[], int size) {
    int i = (size / 2) - 1;
    while (i >= 0) {
      this->heap(arr, size, i);
      i--;
    }
  }
};
int main() {
  minHeap obj;
  int arr[] = {
    4,
    7,
    8,
    2,
    9,
    3,
    1,
    6,
    10
  };
  /*

    initial elements

              4
           /      \
          /        \
         7          8
       /   \       /  \
      2     9     3    1
     / \   
    6   10 
  */
  int size = sizeof(arr)/sizeof(arr[0]);
  cout << "\n Before elements ";
  obj.print_data(arr, size);
  
  obj.min_heap(arr, size);
  /*
    After convert into min heap elements

              1
           /      \
          /        \
         2          3
       /   \       /  \
      6     9     4    8
     / \   
    7   10 
  */


  cout << "\n After Min heap elements ";
  obj.print_data(arr, size);
  return 0;
}

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
/*
Java program
Implement min heap using array
*/

public class MinHeap {
  //swap array element
  public void swap(int []arr, int first, int second) {
    int auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  //compare node value
  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_step = compare(arr, left, right, root, size);

    if (next_step != -1) {
      heap(arr, size, next_step);
    }
  }
  public void print_data(int []arr, int size) {

    System.out.print("\n");

    int i = 0;

    while ( i < size) {

      System.out.print("   "+ arr[i]);

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


  public static void main(String[] args) {


    MinHeap obj = new MinHeap();

    //Array elements
    int []arr = {4, 7, 8, 2, 9, 3, 1, 6, 10};

      /*

      initial elements

                4
             /      \
            /        \
           7          8
         /   \       /  \
        2     9     3    1
       / \   
      6   10 
    */
    //find the length of array elements
    int size = arr.length;

    System.out.print("\n Before elements ");
    //Display array elements
    obj.print_data(arr,size);


    obj.min_heap(arr,size);

    /*
      After convert into min heap elements

                1
             /      \
            /        \
           2          3
         /   \       /  \
        6     9     4    8
       / \   
      7   10 
    */

    System.out.print("\n After Min heap elements ");
    //Display array elements
    obj.print_data(arr,size);

  }
}

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
/*
C# program
Implement min heap using array
*/
using System;
public class MinHeap {
  //swap array element
  public void swap(int []arr, int first, int second) {
    int auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  //compare node value
  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_step = compare(arr, left, right, root, size);

    if (next_step != -1) {
      heap(arr, size, next_step);
    }
  }
  public void print_data(int []arr, int size) {

    Console.Write("\n");

    int i = 0;

    while ( i < size) {

      Console.Write("   "+ arr[i]);

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


  public static void Main(String[] args) {


    MinHeap obj = new MinHeap();

    //Array elements
    int []arr = {4, 7, 8, 2, 9, 3, 1, 6, 10};

    /*

      initial elements

                4
             /      \
            /        \
           7          8
         /   \       /  \
        2     9     3    1
       / \   
      6   10 
    */
    //find the.Length of array elements
    int size = arr.Length;

    Console.Write("\n Before elements ");
    //Display array elements
    obj.print_data(arr,size);


    obj.min_heap(arr,size);

    /*
      After convert into min heap elements

                1
             /      \
            /        \
           2          3
         /   \       /  \
        6     9     4    8
       / \   
      7   10 
    */

    Console.Write("\n After Min heap elements ");
    //Display array elements
    obj.print_data(arr,size);

  }
}

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
# Python 3 Program
# Implement min heap using array

class MinHeap :
  def swap(self, arr, first, second) :
    auxiliary = arr[first]
    arr[first] = arr[second]
    arr[second] = auxiliary
  
  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_step = self.compare(arr, left, right, root, size)
    if (next_step != -1) :
      self.heap(arr, size, next_step)
    
  
  def print_data(self, arr, size) :
  
    i = 0
    while (i < size) :
      print("  ", arr[i],end="")
      i += 1
    
  
  def min_heap(self, arr, size) :
    i = int(size / 2) - 1
    while (i >= 0) :
      self.heap(arr, size, i)
      i -= 1
    
  

def main() :
  obj = MinHeap()
  arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]

  #
  #    initial elements
  #              4
  #           /      \
  #          /        \
  #         7          8
  #       /   \       /  \
  #      2     9     3    1
  #     / \
  #    6   10
  #  
  size = len(arr)
  print("\n Before elements ")
  obj.print_data(arr, size)
  obj.min_heap(arr, size)
  #
  #    After convert into min heap elements
  #              1
  #           /      \
  #          /        \
  #         2          3
  #       /   \       /  \
  #      6     9     4    8
  #     / \
  #    7   10
  #  
  print("\n After Min heap elements ")
  obj.print_data(arr, size)

if __name__ == "__main__":
  main()

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
# Ruby Program
# Implement min heap using array

class MinHeap 
  def swap(arr, first, second) 
    auxiliary = arr[first]
    arr[first] = arr[second]
    arr[second] = auxiliary
  end
  def compare(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
      end
    elsif (right < size and 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_step = self.compare(arr, left, right, root, size)
    if (next_step != -1) 
      self.heap(arr, size, next_step)
    end
  end
  def print_data(arr, size) 
    print("\n")
    i = 0
    while (i < size) 
      print("   ", arr[i])
      i += 1
    end
  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 = MinHeap.new()
  arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]

  #
  #    initial elements
  #              4
  #           /      \
  #          /        \
  #         7          8
  #       /   \       /  \
  #      2     9     3    1
  #     / \
  #    6   10
  #  
  size = arr.length
  print("\n Before elements ")
  obj.print_data(arr, size)
  obj.min_heap(arr, size)
  #
  #    After convert into min heap elements
  #              1
  #           /      \
  #          /        \
  #         2          3
  #       /   \       /  \
  #      6     9     4    8
  #     / \
  #    7   10
  #  
  print("\n After Min heap elements ")
  obj.print_data(arr, size)
end
main()

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
<?php
/*
 Php Program
 Implement min heap using array
*/

class MinHeap {
  public  function swap(&$arr, $first, $second) {
    $auxiliary = $arr[$first];
    $arr[$first] = $arr[$second];
    $arr[$second] = $auxiliary;
  }
  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_step = $this->compare($arr, $left, $right, $root, $size);
    if ($next_step != -1) {
      $this->heap($arr, $size, $next_step);
    }
  }
  public  function print_data($arr, $size) {
    echo("\n");
    $i = 0;
    while ($i < $size) {
      echo("   ". $arr[$i]);
      $i++;
    }
  }
  public  function min_heap(&$arr, $size) {
    $i = intval($size / 2) - 1;
    while ($i >= 0) {
      $this->heap($arr, $size, $i);
      $i--;
    }
  }
}

function main() {
  $obj = new MinHeap();
  $arr = array(4, 7, 8, 2, 9, 3, 1, 6, 10);
  /*

    initial elements

              4
           /      \
          /        \
         7          8
       /   \       /  \
      2     9     3    1
     / \   
    6   10 
  */
  $size = count($arr);
  echo("\n Before elements ");
  $obj->print_data($arr, $size);
  $obj->min_heap($arr, $size);
    /*
      After convert into min heap elements

                1
             /      \
            /        \
           2          3
         /   \       /  \
        6     9     4    8
       / \   
      7   10 
    */

  echo("\n After Min heap elements ");
  $obj->print_data($arr, $size);
}
main();

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
/*
 Node Js Program
 Implement min heap using array
*/

class MinHeap {
  swap(arr, first, second) {
    var auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  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_step = this.compare(arr, left, right, root, size);
    if (next_step != -1) {
      this.heap(arr, size, next_step);
    }
  }
  print_data(arr, size) {
    process.stdout.write("\n");
    var i = 0;
    while (i < size) {
      process.stdout.write("   " + arr[i]);
      i++;
    }
  }
  min_heap(arr, size) {
    var i = parseInt(size / 2) - 1;
    while (i >= 0) {
      this.heap(arr, size, i);
      i--;
    }
  }
}

function main() {
  var obj = new MinHeap();
  var arr = [4, 7, 8, 2, 9, 3, 1, 6, 10];
  /*

    initial elements

              4
           /      \
          /        \
         7          8
       /   \       /  \
      2     9     3    1
     / \   
    6   10 
  */
  var size = arr.length;
  process.stdout.write("\n Before elements ");
  obj.print_data(arr, size);
  obj.min_heap(arr, size);
    /*
      After convert into min heap elements

                1
             /      \
            /        \
           2          3
         /   \       /  \
        6     9     4    8
       / \   
      7   10 
    */
  process.stdout.write("\n After Min heap elements ");
  obj.print_data(arr, size);
}

main();

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10
/*
 Swift 4 Program
 Implement min heap using array
*/

class MinHeap {
  func swap(_ arr: inout [Int] , _ first : Int, _ second: Int) {
    let auxiliary: Int = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  func compare(_ arr: inout [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]) {
        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: Int = 2 * root + 1;
    let right: Int = 2 * root + 2;
    let next_step: Int = self.compare(&arr, left, right, root, size);
    if (next_step != -1) {
      self.heap(&arr, size, next_step);
    }
  }
  func print_data(_ arr: [Int] , _ size : Int) {
  
    var i: Int = 0;
    while (i < size) {
      print("  ", arr[i],terminator:"");
      i += 1;
    }
  }
  func min_heap(_ arr: inout [Int] , _ size : Int) {
    var i: Int = (size / 2) - 1;
    while (i >= 0) {
      self.heap(&arr, size, i);
      i -= 1;
    }
  }
}
func main() {
  let obj: MinHeap = MinHeap();
  var arr: [Int] = [4, 7, 8, 2, 9, 3, 1, 6, 10];
  /*

    initial elements

              4
           /      \
          /        \
         7          8
       /   \       /  \
      2     9     3    1
     / \   
    6   10 
  */
  let size: Int = arr.count;
  print("\n Before elements ");
  obj.print_data(arr, size);
  obj.min_heap(&arr, size);
  /*
    After convert into min heap elements

              1
           /      \
          /        \
         2          3
       /   \       /  \
      6     9     4    8
     / \   
    7   10 
  */

  print("\n After Min heap elements ");
  obj.print_data(arr, size);
}
main();

Output

 Before elements 
  4  7  8  2  9  3  1  6 10
 After Min heap elements 
  1  2  3  6  9  4  8  7 10


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