Answer to Question #204233 in Java | JSP | JSF for Haider

Question

What is heap. Create maximum heap using built in function or using array list. Use any one method for creation max heap.

Answer 1

A heap is a data structure where elements or items are organized on top of each other haphazardly and the tree must be a complete binary for it to be a heap.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package heap;
import java.util.Scanner;


/**
 *
 * @author Student
 */
public class Heap {


  static void heapify_node(int arr[], int s, int n) 
  { 
    int maximum = n;    // Initialize the maximum node to be current node 
    int left_node = 2 * n + 1;   //Left child's position in array is = 2*i + 1 
    int right_node = 2 * n + 2;   //Right child's position in array is = 2*i + 1  
                                             
    if (left_node < s && arr[left_node] > arr[maximum])  // If root is less than left child 
      maximum = left_node; 
    
    if (right_node < s && arr[right_node] > arr[maximum]) // If the maximum root is less than the right child 
      maximum = right_node; 
  
    if (maximum != n) {         // If root is not the maximum, do swapping 
      int swapper = arr[n]; 
      arr[n] = arr[maximum]; 
      arr[maximum] = swapper; 
  
      heapify_node(arr, s, maximum);  
    } 
  } 
  static void Heap_build_node(int array[], int i) 
  { 
    
    int start = (i / 2) - 1; // Index of last non-leaf node 
    for (int n = start; n >= 0; n--) { 
      heapify_node(array, i, n); 
    } 
  } 
  
  static void display_heap(int array[], int node) 
  { 
    System.out.println("Representing heap using an array:"); 
    for (int x = 0; x < node; x++) 
    System.out.print(array[x] + " "); 
    System.out.println(); 
  } 
  
  public static void main(String args[]) 
  {   
      
    Scanner input=new Scanner(System.in);
    System.out.println("Enter array size: ");
    int size = input.nextInt(); 
    int array[]=new int[size];
      
    System.out.println("Enter element of the array: ");
    for(int n=0; n<size; n++)
          array[n] =input.nextInt();
    Heap_build_node(array, size); 
     display_heap(array, size); 
  } 
}