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 

Merge two sorted lists

Merge two sorted lists



/*
  Merge two sorted lists A and B as one linked list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* MergeLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    Node *tmpA = headA, *tmpB = headB, *headC, *tmpC, x;
    headC = &x;
    headC -> next = NULL;
    tmpC = headC;
    while(tmpA != NULL && tmpB != NULL)
        {
        if(tmpA -> data <= tmpB -> data )
            {
            Node *t = tmpA;
            tmpA = tmpA -> next;
            tmpC -> next = t;
            t -> next = NULL;
            }
        else 
            {
            Node *t = tmpB;
            tmpB = tmpB -> next;
            tmpC -> next = t;
            t -> next = NULL;            
        }
        tmpC = tmpC -> next;
    }   
    if(tmpA == NULL)
        tmpC -> next = tmpB;
    if(tmpB == NULL)
        tmpC -> next = tmpA;
    return headC -> next;
}

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.

Detect cycle in linked list

Problem Statement

This challenge is part of a tutorial track by MyCodeSchool

You’re given the pointer to the head node of a linked list. Find whether the list contains any cycle (or loop). A linked list is said to contain cycle if any node is re-visited while traversing the list. The head pointer given may be null meaning that the list is empty.

Input Format 
You have to complete the int HasCycle(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console. Number of nodes in a linked list doesn't exceed 100.

Output Format 
Check whether the linked list has a cycle and return 1 if there is a cycle. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

1 --> NULL

1 --> 2 --> 3
      ^     |
      |     |
       -----                           

Sample Output

0
1

Explanation 
1. First list has no cycle, hence return 0 
2. Second list is shown to have a cycle, hence return 1.

Note 
After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.

Copyright © 2015 HackerRank.
All Rights Reserved

/*
  Detect loop in a linked list 
  List could be empty also
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int HasCycle(Node* head)
{
   // Complete this function
   // Do not write the main method
    Node *hare = head, *tor = head;
    if(head == NULL)
        return 0;
    while(1)
        {
        if(hare -> next == NULL)
            return 0;
        if(hare -> next -> next == NULL)
            return 0;
        hare = hare -> next -> next;
        tor = tor -> next;
        if(tor == hare)
            return 1;
    }
}

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);
}
}

Flowers - greedy

Problem Statement

You and your K−1 friends want to buy N flowers. Flower number i has cost ci. Unfortunately the seller does not want just one customer to buy a lot of flowers, so he tries to change the price of flowers for customers who have already bought some flowers. More precisely, if a customer has already bought x flowers, he should pay (x+1)×ci dollars to buy flower number i. 
You and your K−1 friends want to buy all N flowers in such a way that you spend the least amount of money. You can buy the flowers in any order.

Input:

The first line of input contains two integers N and K(K<=N). The next line contains Nspace separated positive integers c1,c2,...,cN.

Output:

Print the minimum amount of money you (and your friends) have to pay in order to buy all Nflowers.

Constraints

1≤N,K≤100 
Any ci is not more than 106 
Result is guaranteed to be less than 231

Sample input #00

3 3
2 5 6

Sample output #00

13

Sample input #01

3 2
2 5 6

Sample output #01

15

Explanation : 
Sample Case #00: In this example, all of you should buy one flower each. Hence, you'll have to pay 13 dollars. 
Sample Case #01: Here one of the friend buys first two flowers in decreasing order of their price. So he will pay (0+1)*5 + (1+1)*2 = 9. And other friend will buy the costliest flower of cost 6. So total money need is 9+6=15.

Copyright © 2015 HackerRank.
All Rights Reserved

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

public class Solution {

    public static void main(String[] args) throws IOException{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] in = s.split(" ");
        int n = Integer.parseInt(in[0]);
        int k = Integer.parseInt(in[1]);
        s = br.readLine();
        String[] tmp = s.split(" ");
        int[] cost = new int[n];
        for(int i = 0 ; i < n ; i++)
            {
            cost[i] = Integer.parseInt(tmp[i]);
        }
        Arrays.sort(cost);
        int index = 0, total = 0, j = 1;
        for(int i = n - 1 ; i >= 0 ; i--)
            {
            if(j > k)
            {    
                j = 1;
                index++;
            }
            total += (index + 1) * cost[i];
            j++;  
        }
        System.out.println(total);
    }
}