Heap Implementation in JAVA

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).

In a heap, the highest (or lowest) priority element is always stored at the root, hence the name heap. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.

1:  package com.examples.ajay;  
2:  class Heap{  
3:       int[] array;  
4:       int count;  
5:       int capacity;  
6:       int heap_type;  
7:  }  
8:  public class HeapImplementation {  
9:       public static Heap createHeap(int capacity, int heap_type){  
10:            Heap heap = new Heap();  
11:            heap.array = new int[capacity];  
12:            if(heap.array == null) return null;  
13:            heap.heap_type = heap_type;  
14:            heap.count = 0;  
15:            heap.capacity = capacity;  
16:            return heap;  
17:       }  
18:       public static int getParent(Heap heap, int i){  
19:            if(i >= heap.count || i <= 0) return -1; //asking for parent of root or entry outside the amount of elements in heap  
20:            return (i-1)/2;  
21:       }  
22:       public static int leftChild(Heap heap, int i){  
23:            int left = 2*i + 1;  
24:            if(left >= heap.count) return -1;  
25:            else return left;  
26:       }  
27:       public static int rightChild(Heap heap, int i){  
28:            int right = 2*i + 2;  
29:            if(right >= heap.count) return -1;  
30:            else return right;  
31:       }  
32:       public static int getMaximum(Heap heap){  
33:            if(heap.count <= 0) return -1;  
34:            else return heap.array[0];  
35:       }  
36:       public static void heapify(Heap heap , int i){  
37:            int left, right, max;  
38:            left = leftChild(heap, i);  
39:            right = rightChild(heap, i);  
40:            //exchange parent with the maximum among both of left or right children  
41:            if(left != -1 && heap.array[left] > heap.array[i]) max = left;  
42:            else max = i;  
43:            if(right != -1 && heap.array[right] > heap.array[max]) max = right;  
44:            if(max != i){  
45:                 int temp = heap.array[max];  
46:                 heap.array[max] = heap.array[i];  
47:                 heap.array[i] = temp;  
48:                 heapify(heap, max);  
49:            }  
50:       }  
51:       public static int deleteMax(Heap heap){  
52:            int data;  
53:            if(heap.count <= 0) return -1;  
54:            data = heap.array[0];  
55:            heap.array[0] = heap.array[heap.count - 1];  
56:            heap.count--;  
57:            heapify(heap, 0);  
58:            return data;  
59:       }  
60:       public static void insert(Heap heap, int data){  
61:            if(heap.count == heap.capacity) resizeHeap(heap);  
62:            heap.count++;  
63:            int i = heap.count - 1;  
64:            //find location till data is greater than the parent of node which is inserted at count-1  
65:            while(i > 0 && data > heap.array[(i-1)/2]){  
66:                 heap.array[i] = heap.array[(i-1)/2];  
67:                 i = (i-1)/2;  
68:            }  
69:            heap.array[i] = data;  
70:       }  
71:       private static void resizeHeap(Heap heap) {  
72:            // TODO Auto-generated method stub  
73:            int i = 0;  
74:            int[] temp = heap.array;  
75:            heap.array = new int[heap.capacity * 2];  
76:            for (int element : temp) {  
77:                 heap.array[i++] = element;  
78:            }  
79:            heap.capacity *= 2;  
80:       }  
81:       public static void main(String[] args) {  
82:            // TODO Auto-generated method stub  
83:            int[] heapArray = {3, 1, 9, 8, 14, 12, 5, 7, 31, 10, 16};  
84:            Heap heap = createHeap(heapArray.length, 0);  
85:            /*for(int element : heapArray){  
86:                 insert(heap, element);  
87:            }*/  
88:            int i = 0;  
89:            for(int element : heapArray){  
90:                 heap.array[i++] = element;  
91:            }  
92:            heap.count = heapArray.length;  
93:            for(i = (heapArray.length - 1)/2; i >= 0 ; i--) heapify(heap, i);  
94:            System.out.println("Results: ");  
95:            for(i = 0; i < heap.count ; i++){  
96:                 System.out.print(heap.array[i] + " ");  
97:            }  
98:            System.out.println();  
99:            System.out.println("Deleing root ...");  
100:            deleteMax(heap);  
101:            System.out.println("Results: ");  
102:            for(i = 0; i < heap.count ; i++){  
103:                 System.out.print(heap.array[i] + " ");  
104:            }  
105:       }  
106:  }  

Output :

Results: 

31 16 12 9 14 3 5 1 7 8 10 

Deleting root ...

Results: 

16 14 12 9 10 3 5 1 7 8 

Sort elements by frequency

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

Examples:

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

 Input 5  2  2  8  5  6  8  8

  After sorting we get
  Element 2 2 5 5 6 8 8 8
  Index   1 2 0 4 5 3 6 7

  Now construct the 2D array as
  Index, Count
  1,      2
  0,      2
  5,      1
  3,      3

  Sort by count (consider indexes in case of tie)
  3, 3
  0, 2
  1, 2
  5, 1
  
  Print the elements using indexes in the above 2D array.

=================================================

JAVA IMPLEMENTATION

=================================================

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Set;

class Element{

int value;

int index;

int count;

public Element(int value, int index, int count){

this.value = value;

this.index = index;

this.count = count;

}

}

public class SortElementByFrequency {

public static void main(String[] args) {

int array[] = {2, 5, 2, 6, -1, 999999, 5, 8, 8, 8};

int index = 0;

Map<Integer, Element> map = new HashMap<Integer , Element>();

for (int value : array) {

Element element = new Element(value, index, 1);

index++;

if(map.get(element.value) != null){

Element newelement = map.get(element.value);

newelement.count += 1;

map.put(element.value, newelement);

}else{

map.put(element.value, element);

}

}

Set<Integer> keys = map.keySet();

List<Element> list = new ArrayList<Element>();

for (Integer key : keys) {

list.add(map.get(key));

}

Collections.sort(list, new Comparator<Element>() {

@Override

public int compare(Element e1, Element e2) {

// TODO Auto-generated method stub

if(e2.count-e1.count != 0){

return e2.count-e1.count;

}else{

return e1.index-e2.index;

}

}

});

for (Element element : list) {

int count = element.count;

while(count > 0){

System.out.print(element.value + "  ");

count--;

}

}

}

}

Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

package com.examples.ajay;

public class MaxSumNoAdjacentElement {

  private static int max(int i, int j) {

// TODO Auto-generated method stub

if(i < j) return j;

else return i;

}

private static void findSum(int[] array) {

// TODO Auto-generated method stub

int inclusive = array[0]; 
  // Max sum including current element. (If current included, prev     have to be excluded)

int exclusive = 0;
  // Max sum excluding current element : max (prev-incl, prev-excl) 

for(int i = 1; i< array.length; i++){

int temp = inclusive;

inclusive = exclusive + array[i];

exclusive = max(exclusive, temp);

}

System.out.println("Result : "+ max(inclusive, exclusive));

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int array[] = {5, 5, 10, 40, 50, 35};

findSum(array);

}

}

Program for array rotation

Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Rotation of the above array by 2 will make array

METHOD 1 (Use temp array)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2]
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2]

Time complexity O(n)
Auxiliary Space: O(d)

METHOD 2 (Rotate one by one)

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
endTime complexity: O(n*d)

Auxiliary Space: O(1)

METHOD 3 (A Juggling Algorithm)
This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement)



          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b) Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c) Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Java Code for Juggler Algorithm :

package com.examples.ajay;


public class RotateArrrayJugglerWay {

 private static int findGCD(int n, int d){
  if(n % d == 0) return d;
  else return findGCD(d, n % d);
 }
 private static void leftRotate(int[] array, int dist, int length) {
  // TODO Auto-generated method stub
  int gcd = findGCD(length, dist);
  int set_number = length / gcd;
  for(int i =0; i< gcd; i++){
   int temp = array[i];
   int j = i;
   while((j+gcd) < length){
    array[j] = array[j + gcd];
    j = j + gcd;
   }
   array[j] = temp;
  }
  for (int element : array) {
   System.out.print(element + " ");
  }
 }
 public static void main(String[] args) {
  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
  leftRotate(array, 11, array.length);
 }
}

Time complexity: O(n)
Auxiliary Space: O(1)

Method 4(The Reversal Algorithm)
Please read this for first three methods of array rotation.

Algorithm:
rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], l, n);


Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is:
Reverse A to get ArB. /* Ar is reverse of A */
Reverse B to get ArBr. /* Br is reverse of B */
Reverse all to get (ArBr) r = BA.

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
A = [1, 2] and B = [3, 4, 5, 6, 7]
Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]
Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]
Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

Note : Examples and description have been taken from geeksforgeeks.org.

Find Majority Element in an Array : Occurrence more than n/2

import java.util.Scanner;
//Method 1
/*The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break
the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1)

//Method 2
Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


//Method 3  Moore’s Voting Algorithm
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element
e with all the other elements that are different from e then e will exist till end if it is a majority element.

*/

public class FindMajority {
private static int findMajority(int[] array){
int majorityCand = array[0];
int count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
else count--;
if(count == 0){
majorityCand = array[i];
count = 1;
}
}
count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
}
if(count > array.length/2) System.out.println("Majoirty element :" + majorityCand);
else System.out.println("No majority element !!");
return 0;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] array = new int[N];
for(int i = 0; i< N; i++){
array[i] = in.nextInt();
}
findMajority(array);
}
}

Game of Thrones - I

Problem Statement

Dothraki are planning an attack to usurp King Robert's throne. King Robert learns of this conspiracy from Raven and plans to lock the single door through which the enemy can enter his kingdom.

But, to lock the door he needs a key that is an anagram of a certain palindrome string.

The king has a string composed of lowercase English letters. Help him figure out whether any anagram of the string can be a palindrome or not.

Input Format 
A single line which contains the input string.

Constraints 
1≤ length of string ≤105 
Each character of the string is a lowercase English letter.

Output Format 
A single line which contains YES or NO in uppercase.

Sample Input : 01

aaabbbb

Sample Output : 01

YES

Explanation 
A palindrome permutation of the given string is bbaaabb. 

Sample Input : 02

cdefghmnopqrstuvw

Sample Output : 02

NO

Explanation 
You can verify that the given string has no palindrome permutation. 

Sample Input : 03

cdcdcdcdeeeef

Sample Output : 03

YES

Explanation 
A palindrome permutation of the given string is ddcceefeeccdd

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String entry = in.next();
        int[] frequency = new int[26];
        for(int i =0; i<entry.length(); i++){
            char ch = entry.charAt(i);
            frequency[ch - 'a']++;
        }
        int countOdd = 0;
        for(int i = 0; i < 26 ; i++){
            if(frequency[i] % 2 != 0){
                countOdd++;
            }
        }
        if(countOdd > 1) System.out.println("NO");
        else System.out.println("YES");
    }
}

Reverse Shuffle Merge

Problem Statement

Given a string, S, we define some operations on the string as follows:

a. reverse(S) denotes the string obtained by reversing string S. E.g.: reverse("abc") = "cba"

b. shuffle(S) denotes any string that's a permutation of string S. E.g.: shuffle("god") ∈ ['god', 'gdo', 'ogd', 'odg', 'dgo', 'dog']

c. merge(S1,S2) denotes any string that's obtained by interspersing the two strings S1 & S2, maintaining the order of characters in both.
E.g.: S1 = "abc" & S2 = "def", one possible result of merge(S1,S2) could be "abcdef", another could be "abdecf", another could be "adbecf" and so on.

Given a string S such that S∈ merge(reverse(A), shuffle(A)), for some string A, can you find the lexicographically smallest A?

Input Format

A single line containing the string S.

Constraints:
S contains only lower-case English letters.
The length of string S is less than or equal to 10000.

Output Format

A string which is the lexicographically smallest valid A.

Sample Input

eggegg

Sample Output

egg

Explanation

reverse("egg") = "gge"
shuffle("egg") can be "egg"
"eggegg" belongs to merge of ("gge", "egg")

The split is: e(gge)gg.

egg is the lexicographically smallest.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String entry = in.next();
        int[] frequency = new int[26];
        int uniqueElement = 0;
        for(int i =0; i < entry.length(); i++){
            char currentChar = entry.charAt(i);
            if(frequency[currentChar - 'a'] == 0){
                uniqueElement++;
            }
            frequency[currentChar - 'a']++;
        }
        //Halve the frequency of each character to find the frequency the characters in the answer
        for(int i =0; i<26; i++){
            frequency[i] = frequency[i]/2;
        }
        int lastIndex = entry.length();
        StringBuilder result = new StringBuilder(lastIndex/2);
        while(uniqueElement > 0){
            //find the smallest window which have elemnents of frequency as subsequence
            int[] tempFrequency = frequency.clone();
            int tempUniqueElement = uniqueElement;
            int windowSize = 0;
            
            for(int i=0; i < entry.length(); i++){
                char currentChar = entry.charAt(i);
                tempFrequency[currentChar - 'a']--;
                if(tempFrequency[currentChar - 'a'] == 0) tempUniqueElement--;
                if(tempUniqueElement == 0) break;
                windowSize++;
            }
            Character minCharacter = null;
            for(int i= lastIndex - 1; i >= windowSize; i--){
                if(frequency[entry.charAt(i) - 'a'] == 0){
                    continue;
                }
                if(minCharacter == null || minCharacter > entry.charAt(i)){
                    minCharacter = entry.charAt(i);
                    lastIndex = i;
                }
            }
            result.append(minCharacter);
            frequency[minCharacter - 'a']--;
            if(frequency[minCharacter - 'a'] == 0){
                uniqueElement--;
            }
        }
        System.out.println(result.toString());
    }
}