Min Heap and Max Heap in Java

Min Heap and Max Heap in Java.


In this post we will see what is Min Heap, Max Heap, the operation it supports and the time and space complexity of each operation.

Complete Binary Tree.

Min Heap and Max Heap uses the concept of Complete Binary Tree.

A heap (Binary heap here) is a complete binary tree which satisfies below property,

Min-heap: the value of each node is greater than or equal to the value of its parent, that is the element with minimum value is always at the root. 
Max-heap: the value of each node is less than or equal to the value of its parent, that is the element with maximum value is always at the root.

If we represent the array as Complete Binary tree, how is left child and right child index calculated?
Check this link which explains heap concepts in detail Heap Sort Algorithm

In this post, we will implement Min Heap and the operation it support would be,
  • add - this will add a element to a heap
  • remove - this will remove a element from a heap
  • peek - this will give you a minimum element in a heap
Time complexity of each operation,
  • add - O(log n)
  • remove - O(log n)
  • peek - O(1)
Since in addition/removal, new element added/removed could disturb the heap property so we have to scan all the elements belonging to height of binary tree which take Log n operation.

Min Heap in Java


 
package javabypatel.heap;

public class MinHeap {
    private int[] heap;
    private int size;
    private int currentIndex=-1;

    public MinHeap(int size) {
        this.heap = new int[size];
        this.size = size;
    }

    public int remove() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        int temp = heap[0];
        heap[0] = heap[currentIndex];
        currentIndex--;
        bubbleDown(0);
        return temp;
    }

    public int peek() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        return heap[0];
    }

    public void add(int data) {
        if ((currentIndex + 1) >= size) {
            throw new RuntimeException("Heap full");
        }

        heap[++currentIndex] = data;
        bubbleUp(currentIndex);
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private boolean isParentPresent(int index) {
        return getParentIndex(index) >= 0;
    }

    private void bubbleUp(int index) {
        if (!isParentPresent(index)) {
            return;
        }

        int parentIndex = getParentIndex(index);

        if (heap[index] < heap[parentIndex]) {
            swap(index, parentIndex);
            bubbleUp(parentIndex);
        }
    }

    private void bubbleDown(int index) {
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int minIndex = index;
        if (left <= currentIndex && heap[left] < heap[minIndex]) {
            minIndex = left;
        }
        if (right <= currentIndex && heap[right] < heap[minIndex]) {
            minIndex = right;
        }

        if (index != minIndex) {
            swap(index, minIndex);
            bubbleDown(minIndex);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

 
package javabypatel.heap;

public class MinHeapMain {
    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.add(5);
        minHeap.add(1);
        System.out.println(minHeap.peek());
        minHeap.remove();
        minHeap.add(4);
        System.out.println(minHeap.peek());
        minHeap.add(2);
        System.out.println(minHeap.peek());
    }
}
Output: 

Max Heap is very similar to Min Heap, except we keep the maximum at the top.

Max Heap in Java

package javabypatel.heap;

public class MaxHeap {
    private int[] heap;
    private int size;
    private int currentIndex=-1;

    public MaxHeap(int size) {
        this.heap = new int[size];
        this.size = size;
    }

    public int remove() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        int temp = heap[0];
        heap[0] = heap[currentIndex];
        currentIndex--;
        bubbleDown(0);
        return temp;
    }

    public int peek() {
        if (currentIndex < 0) {
            throw new RuntimeException("Heap is empty");
        }
        return heap[0];
    }

    public void add(int data) {
        if ((currentIndex + 1) >= size) {
            throw new RuntimeException("Heap full");
        }

        heap[++currentIndex] = data;
        bubbleUp(currentIndex);
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private boolean isParentPresent(int index) {
        return getParentIndex(index) >= 0;
    }

    private void bubbleUp(int index) {
        if (!isParentPresent(index)) {
            return;
        }

        int parentIndex = getParentIndex(index);

        if (heap[index] > heap[parentIndex]) {
            swap(index, parentIndex);
            bubbleUp(parentIndex);
        }
    }

    private void bubbleDown(int index) {
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int minIndex = index;
        if (left <= currentIndex && heap[left] > heap[minIndex]) {
            minIndex = left;
        }
        if (right <= currentIndex && heap[right] > heap[minIndex]) {
            minIndex = right;
        }

        if (index != minIndex) {
            swap(index, minIndex);
            bubbleDown(minIndex);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

}
package javabypatel.heap;

public class MaxHeapMain {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.add(5);
        maxHeap.add(1);
        System.out.println(maxHeap.peek());
        maxHeap.remove();
        System.out.println(maxHeap.peek());
        maxHeap.add(15);
        System.out.println(maxHeap.peek());
        maxHeap.add(20);
        System.out.println(maxHeap.peek());
    }
}
Output: 
15 
20

Find the angle between the hour and minute hands in Java

Find the angle between the hour and minute hands on an analog clock.


Given the time, calculate the smaller angle between the hour and minute hands on an analog clock in Java.

Java Program to find angle between hour and minute hand.


In 60 mins, clock minute hand takes 360 degree. so for 1 min = 360/60 = 6 degree.
In 12 hours, clock hour hand takes 360 degree. so for 1 hour = 360/12 = 30 degree 

But when it is 1.20, hour hand doesn't be on exact 1, and would be slightly crossed 1 (when it is 1.30, hour hand would be in between 1 and 2.) 
So we need to find out the exact position of the hour hand and the angle it covered, that is you need to find the angle hour hand makes for each minute passes. 

We already know 1 hour angle = 30 degree 
In 1 hour, we have 60 minutes, so in each minute, how much angle hour hand makes = 30/60 = 1/2.
 
package javabypatel.misc;

public class FindAngle {
    public static void main(String[] args) {
        System.out.println(findAngle(12, 25));
    }

   public static double findAngle(int hour, int minute) {
        // in 60 mins, it takes 360 degree. so for a 1 min = 360/60 = 6 degree
        double minAngle = minute * 6;

        // in 12 hours, it takes 360 degree. so for 1 hour = 360/12 = 30 degree
       double hourAngle = hour * 30;

        //but when it is 1.20, hour hand doesn't be on exact 1, and would be slightly crossed 1 (when it is 1.30, hour hand would be in between 1 and 2.)
        //So you need to find out the exact position of the hour hand and the angle it covered between a single hour.
        //that is you need to find the angle hour hand makes for each minute passes.
        //we already know 1 hour angle = 30 degree
        //In 1 hour, we have 60 minutes, so in each minute, how much angle hour hand makes = 30/60 = 1/2.
        double hourAngleForEachMinute = minute/2.0; //minute * 1/2; (divided by 2.0 to make it divide in double context)

        //Final hour angle would be hourAngle + hourAngleForEachMinute
        double finalHourAngle = hourAngle + hourAngleForEachMinute;

        double angle = Math.abs(finalHourAngle - minAngle);

        //analog clock is round, so clock hands make two angles, one in interior and one is exterior, Since we are told to return smaller angle we return minimum one.
        return Math.min(angle, 360-angle);
    }
}


Visitor Design Pattern real world example in Java

Visitor Design Pattern real world example in Java


In this post we will see when to use visitor design pattern and the real life example of visitor design pattern in Java.

Scenario for understanding Visitor Design Pattern.

Consider a scenario below,

You own a small supermarket selling items of multiple category ranging from Electronics, Hardware, Plastic, Packaged food, Fresh fruit etc.
  • Supermarket have return policy based on the item category.
  • Supermarket provide discounts based on the item category.
  • Supermarket have different shipping vendor based on item category. (say you purchased an item from e-commerce company like Amazon and now you want to return it. In some countries, they arrange a person to visit your place for picking the item. In some countries, they email you pre-paid shipping label from standard transportation companies like Canada post, UPS etc and you have to pack the item, stick the shipping label and handover to the shipping provider.)
too much explanation... :) lets look into how above scenario can be designed without using visitor design pattern and then we will see benefits of visitor pattern and how it helps in maintaining Open/Closed and Single Responsibility Principle.


For each different category we have to apply different rules in terms of discounts, return policy and shipping vendor.

Problem without Visitor Design Pattern.


We have multiple product category and each have the name, discount, return policy and shipping vendor. we would design something like below,

interface ProductCategory {
String getName();
int discount();
String shippingVendor();
int returnPolicy();
}

class Plastic implements ProductCategory {
@Override
public String getName() {
return "Plastic";
}

@Override
public int discount() {
return 5;
}

@Override
public String shippingVendor() {
return "UPS";
}

@Override
public int returnPolicy() {
return 30;
}
}

class Electronics implements ProductCategory {
@Override
public String getName() {
return "Electronics";
}

@Override
public int discount() {
return 10;
}

@Override
public String shippingVendor() {
return "Canada Post";
}

@Override
public int returnPolicy() {
return 60;
}
}

Now, Imagine you have to add one more rule say packaging type for each category. what we will do is modify the interface to add one more method, 

interface ProductCategory {
String getName();
int discount();
String shippingVendor();
int returnPolicy();
String packingType(); //added
}
You have to modify all the implementation to have this packing type. which is against Open/Closed principle.

Also, responsibility like Discounts, return policy are segregated into each implementation and not at one place.
  
Lets see the sample implementation with Visitor Design pattern now,

Visitor Design Pattern.

With Visitor Design pattern, all such rules that can be applied to each product category is separated from category itself.

Example: Electronics category will not have any implementation details for discounts, return policy, shipping vendor etc as those are the rules that could be added/removed to each category and could change.

so what we would be doing is to allow Electronics category having a visitor called ProductCategoryVisitor (which could be of type DiscountVisitor, ShippingVendorVisitor, ReturnPolicyVisior etc).  

package fresh.armaan;

public class VisitorDesignPattern {

public static void main(String[] args) {
ProductCategoryVisitor discountVisitor = new DiscountVisitor();
ProductCategoryVisitor returnPolicyVisitor = new ReturnPolicyVisitor();

//Plastic
ProductCategory plasticCategory = new Plastic();
System.out.println("Category Name : " + plasticCategory.getName());
System.out.println("Discounts on Plastic Category : " + plasticCategory.visit(discountVisitor) + "%");
System.out.println("Return Policy on Plastic Category : " + plasticCategory.visit(returnPolicyVisitor) + " days");

System.out.println("------------------");

//Electronics
ProductCategory electronicsCategory = new Electronics();
System.out.println("Category Name : " + electronicsCategory.getName());
System.out.println("Discounts on Electronics Category : " + electronicsCategory.visit(discountVisitor) + "%");
System.out.println("Return Policy on Electronics Category : " + electronicsCategory.visit(returnPolicyVisitor) + " days");
}
}

interface ProductCategory {
String getName();
String visit(ProductCategoryVisitor visitor);
}

class Plastic implements ProductCategory {
@Override
public String getName() {
return "Plastic";
}

@Override
public String visit(ProductCategoryVisitor visitor) {
return visitor.visit(this);
}
}

class Electronics implements ProductCategory {
@Override
public String getName() {
return "Electronics";
}

@Override
public String visit(ProductCategoryVisitor visitor) {
return visitor.visit(this);
}
}

interface ProductCategoryVisitor {
String visit(Electronics electronics);
String visit(Plastic plastic);
}

class DiscountVisitor implements ProductCategoryVisitor {

@Override
public String visit(Electronics electronics) {
return "10";
}

@Override
public String visit(Plastic plastic) {
return "5";
}
}

class ReturnPolicyVisitor implements ProductCategoryVisitor {

@Override
public String visit(Electronics electronics) {
return "60";
}

@Override
public String visit(Plastic plastic) {
return "30";
}
}
 
Output:
Category Name : Plastic
Discounts on Plastic Category : 5%
Return Policy on Plastic Category : 30 days
------------------
Category Name : Electronics
Discounts on Electronics Category : 10%
Return Policy on Electronics Category : 60 days
Use visitor pattern when you have a fairly stable class hierarchy (like in our example we have product category Electronics, Plastic etc which changes but not very frequently), but have changing requirements of what needs to be done with that hierarchy (in our example each product category have discounts, return policy, shipping vendor and so on and that could add/remove/change very often), in that case visitor pattern is helpful.

You may also like to see


Advanced Java Multithreading Interview Questions & Answers

Type Casting Interview Questions and Answers In Java?

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

How is ambiguous overloaded method call resolved in java?

Method Overriding rules in Java

Interface interview questions and answers in Java


Enjoy !!!! 
If you find any issue in post or face any error while implementing, Please comment.