Implement Max Heap and Min heap in Java

Problem statement:- Implement Max and Min heap. Display elements in Ascending and Descending order. i.e: Max heap will display elements in Descending order and Min heap display elements in Ascending order.

A min-heap is a binary tree such that -
1. the data contained in each node is less than (or equal to) the data in that node’s children.
2. the binary tree is complete.

A max-heap is a binary tree such that -
1. the data contained in each node is greater than (or equal to) the data in that node’s children.
2. the binary tree is complete.

Sample program implementing max and min heap :-

public class MaxMeanHeap {
public static void main(String[] args) {
 CustomHeap chmax = new CustomHeap(256, 0);
 System.out.println("===========Max Heap creation=========");
 chmax.insert(12);
 chmax.insert(23);
 chmax.insert(2);
 chmax.insert(112);
 chmax.insert(22);
 chmax.insert(3);
 chmax.insert(27);
 chmax.insert(1);

 chmax.displayHeap();
 System.out.println("===========Min Heap creation=========");
 CustomHeap chmin = new CustomHeap(256, 1);
 chmin.insert(12);
 chmin.insert(23);
 chmin.insert(2);
 chmin.insert(112);
 chmin.insert(112);
 chmin.insert(2);
 chmin.insert(53);
 chmin.displayHeap();
 System.out.println("=====Descending order display: Heap sort====");
 chmax.printAscOrder(8);
 System.out.println("======Ascending order dispplay: Heap sort=======");
 chmin.printDscOrder(7);
}

}

class CustomHeap {
int[] heap;
int size;
int minMaxFlag;

public CustomHeap() {
}

public CustomHeap(int max, int minMaxFlag) {
 heap = new int[max];
 size = 0;
 this.minMaxFlag = minMaxFlag;
}

public int getSize() {
 return size;
}

int getTop() {
 int max = Integer.MAX_VALUE;

 if (size >= 0) {
  max = heap[0];
 }

 return max;
}

public int parentIndex(int index) {
 return (index - 1) / 2;
}

public int leftChildIndex(int index) {
 return (2 * index) + 1;
}

public int rightChildIndex(int index) {
 return (2 * index) + 2;
}

public void swap(int index1, int index2) {
 heap[index1] = heap[index1] ^ heap[index2];
 heap[index2] = heap[index1] ^ heap[index2];
 heap[index1] = heap[index1] ^ heap[index2];
}

public void insert(int element) {
 if (size == 0) {
  heap[size++] = element;
 } else {
  heap[size] = element;
  percolateUp(size++);
 }
}

// max/min heap based on flag
public void percolateUp(int index) {
 int temp = heap[index];
 int parent = parentIndex(index);
 if (this.minMaxFlag == 0) {
  while (index > 0 && heap[parent] < temp) {
   heap[index] = heap[parent];
   index = parent;
   parent = parentIndex(index);

  }
 } else {
  while (index > 0 && heap[parent] > temp) {
   heap[index] = heap[parent];
   index = parent;
   parent = parentIndex(index);

  }
 }

 heap[index] = temp;
}

public int remove() {
 int temp = heap[0];
 heap[0] = heap[--size];
 percolateDown(0);
 return temp;
}

public void percolateDown(int index) {
 int lcIndex;
 int rcIndex;
 int temp = heap[index];
 int largeChildIndex;
 int smallChilIndex;
 if (minMaxFlag == 0) {
  while (index < (size / 2)) {
   lcIndex = leftChildIndex(index);
   rcIndex = rightChildIndex(index);
   if (rcIndex < size && heap[lcIndex] < heap[rcIndex]) {
    largeChildIndex = rcIndex;
   } else {
    largeChildIndex = lcIndex;
   }
   if (heap[largeChildIndex] <= temp)
    break;
   heap[index] = heap[largeChildIndex];
   index = largeChildIndex;
  }
 } else {
  while (index < (size / 2)) {
   lcIndex = leftChildIndex(index);
   rcIndex = rightChildIndex(index);
   if (rcIndex < size && heap[lcIndex] > heap[rcIndex]) {
    smallChilIndex = rcIndex;
   } else {
    smallChilIndex = lcIndex;
   }
   if (heap[smallChilIndex] >= temp)
    break;
   heap[index] = heap[smallChilIndex];
   index = smallChilIndex;
  }
 }
 heap[index] = temp;
}

public void printAscOrder(int n) {

 for (int i = 0; i < n; i++) {
  System.out.print(remove() + "\t");
 }
 System.out.println("\n\n");
}

public void printDscOrder(int n) {

 for (int i = 0; i < n; i++) {
  System.out.print(remove() + "\t");
 }
}

public void displayHeap() {
 System.out.print("Inserted elements are: ");
 for (int m = 0; m < size; m++)
  if (heap[m] != Integer.MAX_VALUE)
   System.out.print(heap[m] + " ");
  else
   System.out.print("-- ");
 System.out.println();
 int nBlanks = 32;
 int itemsPerRow = 1;
 int column = 0;
 int j = 0; // current item
 String delimeter = "---------------------------------------------";
 System.out.println(delimeter);
 while (size > 0) {
  if (column == 0)
   for (int k = 0; k < nBlanks; k++)
    System.out.print(' ');
  System.out.print(heap[j]);
  if (++j == size) // done?
   break;
  if (++column == itemsPerRow) {
   nBlanks /= 2;
   itemsPerRow *= 2;
   column = 0;
   System.out.println();
  } else
   for (int k = 0; k < nBlanks * 2 - 2; k++)
    System.out.print(' ');
 }
 System.out.println("\n" + delimeter);
}
}

Explanation:-
The underlying data structure used for implementing Heap is Array. We have used falg "minMaxFlag" to distinguish between max and min heap.For max heap minMaxFlag = 0 and min heap minMaxFlag =1.
In insert() method, percolateUp() is called.Depending on value of flag "minMaxFlag" - percolate method execute corresponding while loop to maintain corresponding heap property. Similarly, in percolateDown() which is called form remove() method, depending on value of flag "minMaxFlag" while loop executed to maintain heap property.

Sample output:-
===========Max Heap creation=========
Inserted elements are: 112 23 27 12 22 2 3 1
---------------------------------------------
                                112
                23                              27
        12              22              2              3
    1
---------------------------------------------
===========Min Heap creation=========
Inserted elements are: 2 23 2 112 112 12 53
---------------------------------------------
                                2
                23                              2
        112              112              12              53
---------------------------------------------
=====Descending order display: Heap sort====
112 27 23 22 12 3 2 1


======Ascending order dispplay: Heap sort=======
2 2 12 23 53 112 112

Longest Common Subsequence in Java

Problem : Given two sequences, find the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.(Reference GeekForGeeks).
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Solution using Recursion:- Order of 2ⁿ

static public int LCSRecursiveSolution(char[] arr1, char[] arr2, int m,
		int n) {
	if (m == 0 || n == 0) {
		return 0;
	}
	if (arr1[m - 1] == arr2[n - 1]) {
		return 1 + LCSRecursiveSolution(arr1, arr2, m - 1, n - 1);
	}
	return Math.max(LCSRecursiveSolution(arr1, arr2, m, n - 1),
			LCSRecursiveSolution(arr1, arr2, m - 1, n));
}

Using dynamic programming :-

static public int LCSUsingDynamicProgramming(char[] arr1, char[] arr2,
		int m, int n) {
	int[][] solution = new int[m + 1][n + 1];
	for (int i = 0; i < m; i++) {
		solution[0][i] = 0;
	}
	for (int i = 0; i < n; i++) {
		solution[i][0] = 0;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr1[i - 1] == arr2[j - 1]) {
				solution[i][j] = solution[i - 1][j - 1] + 1;
			} else {
				solution[i][j] = Math.max(solution[i - 1][j],
						solution[i][j - 1]);
			}
		}
	}
	printLCS(solution, arr1, arr2, m, n);
	return solution[m][n];
}

Display longest common subsequence:-

static void printLCS(int[][] solution, char[] arr1, char[] arr2, int m,
		int n) {
	int i = m;
	int j = n;
	int index = 0;
	char[] result = new char[solution[m][n]];
	
	while (i > 0 && j > 0) {
		if (arr1[i - 1] == arr2[j - 1]) {
			result[index] = arr1[i-1];
			i--;
			j--;
			index++;
		} else if (solution[i][j - 1] > solution[i - 1][j]) {
			j = j - 1;
		} else {
			i = i - 1;
		}
	}
	System.out.println(result);
}

Complete sample program :-

package com.ds.dp;

public class LCSUsingDP {

public static void main(String[] args) {
	char X[] = "AGGTAB".toCharArray();
	char Y[] = "GXTXAYB".toCharArray();
	// System.out.println(LCSRecursiveSolution(X, Y, X.length, Y.length));
	System.out.println("Length of lcs is: "
			+ LCSUsingDynamicProgramming(X, Y, X.length, Y.length));

}

static public int LCSRecursiveSolution(char[] arr1, char[] arr2, int m,
		int n) {
	if (m == 0 || n == 0) {
		return 0;
	}
	if (arr1[m - 1] == arr2[n - 1]) {
		return 1 + LCSRecursiveSolution(arr1, arr2, m - 1, n - 1);
	}
	return Math.max(LCSRecursiveSolution(arr1, arr2, m, n - 1),
			LCSRecursiveSolution(arr1, arr2, m - 1, n));
}

static public int LCSUsingDynamicProgramming(char[] arr1, char[] arr2,
		int m, int n) {
	int[][] solution = new int[m + 1][n + 1];
	for (int i = 0; i < m; i++) {
		solution[0][i] = 0;
	}
	for (int i = 0; i < n; i++) {
		solution[i][0] = 0;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr1[i - 1] == arr2[j - 1]) {
				solution[i][j] = solution[i - 1][j - 1] + 1;
			} else {
				solution[i][j] = Math.max(solution[i - 1][j],
						solution[i][j - 1]);
			}
		}
	}
	printLCS(solution, arr1, arr2, m, n);
	return solution[m][n];
}

static void printLCS(int[][] solution, char[] arr1, char[] arr2, int m,
		int n) {
	int i = m;
	int j = n;
	int index = 0;
	char[] result = new char[solution[m][n]];

	while (i > 0 && j > 0) {
		if (arr1[i - 1] == arr2[j - 1]) {
			result[index] = arr1[i - 1];
			i--;
			j--;
			index++;
		} else if (solution[i][j - 1] > solution[i - 1][j]) {
			j = j - 1;
		} else {
			i = i - 1;
		}
	}
	System.out.print("longest lcs: ");
	System.out.println(result);
}
}

Sample output:-
longest lcs: BATG
Length of lcs is: 4