Heap : build max , min heap, delete root/1st node , print

Heap_BuildHeap_heapifyMin_Max_Delete.java

package ds9thNovNight;
/**
 * 
 * @author Hariom Yadav - Nov 9, 2019
 *build max heap from array, build min heap, delete root node i.e. delete 1st node and internally calls heapify (min or max)
 */
//data structure used is array
public class Heap_BuildHeap_heapifyMin_Max_Delete {
	public static void main(String[] args) {
		int[] arr = {12,1,3,34,9,5};
		int len = arr.length;
		//build heap
		for(int i:arr)
			System.out.print(i+" ");
		System.out.println();
		
		buildHeap(arr, len);
		
		for(int i:arr)
			System.out.print(i+" ");
		int key = 12;
		System.out.println();
		System.out.println("len :"+ len);
		len = deleteRootNode(arr, len, key);//or call as delete 1st index node from array
		System.out.println("len :"+ len);
		
		for(int i=0; i<len; i++)
			System.out.print(arr[i]+" ");
		
		//building min heap : internally calls min heapify
		buildHeapMin(arr, len);
		System.out.println();
		for(int i=0; i<len; i++)
			System.out.print(arr[i]+" ");
		
		
		
	}
	/**
	 * Delete 1st index from array (heap array) and then internally call heapify to make heap array
	 * @param arr 
	 * @param len 
	 * @param key 
	 * @return
	 */
	private static int deleteRootNode(int[] arr,int len, int key) {

		//1 swap with last index value
		arr[0] = arr[len - 1];//len - 1 will give 1st index
		
		//2 decrease length
		--len;
		
		//call heapify
		heapify(arr, len,0);// len is new len that is less than input , 0 is index that value is changed
		
		return len;
	}
	/**
	 * Build heap from given array
	 * @param arr
	 * @param len
	 */
	private static void buildHeap(int[] arr, int len) {
		//find non leaf node
		int nn = (len/2) -1;
		for(int i=nn; i>=0; i--) {
			heapify(arr, len, i);
		}
	}
	
	private static void buildHeapMin(int[] arr, int len) {
		//find non leaf node
		int nn = (len/2) -1;
		for(int i=nn; i>=0; i--) {
			heapifyMin(arr, len, i);
		}
	}
	
	/**
	 * make root as max
	 * @param arr
	 * @param len
	 * @param index
	 */
	private static void heapify(int[] arr, int len, int index) {
		//find all index
		int largest = index;
		int left = index*2 + 1;
		int right = index*2 +2;
		
		//find largest value index
		if(left < len && arr[left] > arr[largest])//largest update
			largest = left;
		if(right < len && arr[right] > arr[largest])//largest updated 
			largest = right;
		
		//if largest not same as index root then swap + call hepify
		if(largest != index) {
			//swap
			int t = arr[index];
			arr[index] = arr[largest];
			arr[largest] = t;
			
			//call heapify
			heapify(arr, len, largest);
		}
	}
	
	private static void heapifyMin(int[] arr, int len, int index) {
		//find all index
		int largest = index;
		int left = index*2 + 1;
		int right = index*2 +2;
		
		//find largest value index
		if(left < len && arr[left] < arr[largest])//largest update
			largest = left;
		if(right < len && arr[right] < arr[largest])//largest updated 
			largest = right;
		
		//if largest not same as index root then swap + call hepify
		if(largest != index) {
			//swap
			int t = arr[index];
			arr[index] = arr[largest];
			arr[largest] = t;
			
			//call heapify
			heapify(arr, len, largest);
		}
	}

}