Heap Sort Java Program

This tutorial shows how to write Heap sort program in Java which is an in-place sorting algorithm. Heap sort uses heap data structure for sorting the elements so the obvious question is what is heap?

Heap data structure

A heap is a binary tree so each node can have maximum two children and it has following properties-

  1. It is a complete binary tree which means reading from left to right it is completely filled in (all the nodes have 2 children) except the last row which need not be full.
  2. Each node in the heap satisfies the condition that each node is greater than or equal to its child nodes in case of Max heap. Node is less than or equal to its child nodes in case of Min heap.
Heap data structure

Heap sort algorithm

Steps for writing the Heap Sort Java program are as follows-

  1. Create a max heap from input array. Using max heap sorting will be done in ascending order. For descending order you can use min heap. Heap data structure is also represented using array. This process of creating heap from the input array is called heapify.
  2. Once the heap is created its root node is the maximum element. Swap the root element with the last element of the array.
  3. This swapping disturbs the heap so structure has to be heapified again using the array. This time last element is excluded (array length decreased by one) as it is already at its final place.
  4. Repeat step 2 and 3 until sorting is complete.

How to create heap from array

Creating heap from an array is an important part of heap sort so understanding it is important.

Array is considered as a complete binary tree with each element considered as a node. With in an array for each node you can get its parent node, left child node and right child node using the following equations-

For a node at index i in the array-

  • Parent node is– (i-1)/2
  • Left child node is- 2*i + 1
  • Right child node is- 2*i+2

To create a heap you'll have to start from the nodes at the bottom and move upwards comparing if child node is greater than the parent and swapping node values if that is true. Since last level has leaf nodes (nodes with no children) so this comparison has to be started from one level above.

For an array of length n, last node will be at index (n-1) thus the index of its parent node should be (n-1)/2 using the equation. Heapifying the array starts from this parent node, in each iteration compare the parent node with left child and right child and swap the nodes if child is greater than the parent.

For example if input array is [5, 12, 3, 16, 8, 10] then the complete binary tree for this array can be visually represented as-

Binary tree

Since last index is 5 thus the parent node should be at index (5-1)/2 = 2. Process of creating a heap starts from that index 2. Compare node at index 2 with its child nodes and swap if any of the child is greater than the parent node. In our tree 10 > 3 so these values are swapped. When index is 1, node at index 1 is compared with its child nodes and values swapped if required.

heap sort

In next iteration comparison and swapping is done for index 0.

Heap Sort Java

Heap Sort Java program

public class HeapSort {

  public static void main(String[] args) {
    int[] arr = {5, 12, 3, 16, 8, 10};	
    System.out.println("Original array- " + Arrays.toString(arr));
    HeapSort hs = new HeapSort();
    hs.heapSort(arr);
    System.out.println("Sorted array after heap sort- " + Arrays.toString(arr));
  }
	
  private void heapSort(int[] arr){
    int arrLength = arr.length;
    // create heap from array start from index (n-1)/2
    for(int i = (arrLength-1)/2; i >= 0; i--){
      heapify(arr, arrLength, i);
    }
    System.out.println("heapified array- " + Arrays.toString(arr));
    // Heap Sort 
    for(int i = arrLength-1; i >= 0; i--){
      // Swap root and last nodes 
      swap(arr, i, 0);
      // Reconstruct heap again 
      heapify(arr, i, 0);
    }
  }
    
  private void heapify(int[] numArr, int index, int i){
    // Getting parent and children indexes
    int root = i;
    int leftChild = 2*i + 1;
    int righChild = 2*i + 2;
    //compare left child value
    if(leftChild < index && numArr[leftChild] > numArr[root])
      root = leftChild;
    //comparing right child value
    if(righChild < index && numArr[righChild] > numArr[root])
      root = righChild;
      // swap values if required and call method recursively for next level
      if(root != i){
        swap(numArr, root, i);
        heapify(numArr, index, root);
      }
    }
    
    private void swap(int[] numArr, int index, int li){
      int temp = numArr[li];
      numArr[li] = numArr[index];
      numArr[index] = temp;
    }
}

Heap sort time and space complexity

Time required to do any common tree operation is O(logn). For Heap sort creation of heap is done for n elements thus the time complexity of Heap sort is O(n*logn). This time complexity remains the same however the data is distributed. That’s where Heap sort scores over Quick sort which is another O(n*logn) sorting algorithm. In worst case Quick sort may become O(n2) but Heap sort is always O(n*logn).

Since same array is used for arranging the elements in order so no extra space requirement is there. Thus the space complexity of Heap sort is O(1).

That's all for the topic Heap Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

How to Synchronize Java HashMap

This post shows how to synchronize HashMap in Java and the HashMap’s thread safe alternative which can be used.

HashMap is not thread safe

If HashMap is accessed by multiple threads concurrently and at least one of the threads modifies the map structurally, you must synchronize HashMap externally. Note that structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.

Options for thread-safe Map

If you want to synchronize HashMap in Java or looking for a thread-safe alternative of HashMap then there are following options.

  1. Use Collections.synchronizedMap() to synchronize Map- This method returns a synchronized (thread-safe) map backed by the specified map. In case you are synchronizing a TreeMap which is a sorted Map you can use synchronizedSortedMap() method
  2. Using ConcurrentHashMap- Another option is to use ConcurrentHashMap from the java.util.concurrent package. All of its operations are thread-safe and it provides better concurrency. ConcurrentHashMap provides better performance by using separate locks for separate buckets rather than synchronizing the whole Map on a single lock.

Using Collections.synchronizedMap()

You can synchronize your HashMap by using Collections.synchronizedMap() method. First we’ll see an example what happens if HashMap is used in a multi-threaded environment without synchronizing it.

In the Java example four threads are created, each of these thread adds 5 elements to the Map. After all the threads are done Map size should be 20.

import java.util.HashMap;
import java.util.Map;

public class MapSynchro implements Runnable{
  private Map<String, String> testMap;
  public MapSynchro(Map<String, String> testMap){
    this.testMap = testMap;
  }

  public static void main(String[] args) {
    // Synchronized Map
    Map<String, String> testMap = new HashMap<String, String>();
    /// 4 threads
    Thread t1 = new Thread(new MapSynchro(testMap));
    Thread t2 = new Thread(new MapSynchro(testMap));
    Thread t3 = new Thread(new MapSynchro(testMap));
    Thread t4 = new Thread(new MapSynchro(testMap));
    
    t1.start();
    t2.start();
    t3.start();
    t4.start();
        
    try {
      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (InterruptedException e) {    
      e.printStackTrace();
    }
    System.out.println("Size of Map is " + testMap.size());
  }
    
  @Override
  public void run() {
    System.out.println("in run method" + Thread.currentThread().getName());
    String str = Thread.currentThread().getName();
    for(int i = 0; i < 5; i++){
      // adding thread name to make element unique
      testMap.put(str+i, str+i);
      try {
        // delay to verify thread interference
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}
Output
in run methodThread-1
in run methodThread-0
in run methodThread-2
in run methodThread-3
Size of Map is 19

In different run I got different HashMap sizes, 17, 18, 19 and 20 because of the thread interference.

Now, if we synchronize the HashMap in the same Java example using Collections.synchronizedMap() method.

public class MapSynchro implements Runnable{
  private Map<String, String> testMap;
  public MapSynchro(Map<String, String> testMap){
    this.testMap = testMap;
  }

  public static void main(String[] args) {
    // Synchronized Map
    Map<String, String> testMap = Collections.synchronizedMap(new HashMap<String, String>());
    /// 4 threads
    Thread t1 = new Thread(new MapSynchro(testMap));
    Thread t2 = new Thread(new MapSynchro(testMap));
    Thread t3 = new Thread(new MapSynchro(testMap));
    Thread t4 = new Thread(new MapSynchro(testMap));
    
    t1.start();
    t2.start();
    t3.start();
    t4.start();
        
    try {
      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (InterruptedException e) {    
      e.printStackTrace();
    }
    System.out.println("Size of Map is " + testMap.size());
  }
  @Override
  public void run() {
    System.out.println("in run method" + Thread.currentThread().getName());
    String str = Thread.currentThread().getName();
    for(int i = 0; i < 5; i++){
      // adding thread name to make element unique
      testMap.put(str+i, str+i);
      try {
        // delay to verify thread interference
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}
Output
in run methodThread-2
in run methodThread-0
in run methodThread-3
in run methodThread-1
Size of Map is 20

Now the size of Map is 20 every time.

Using ConcurrentHashMap

Other than synchronizing HashMap, another option to have a thread safe HashMap is to use ConcurrentHashMap in Java. Let’s see the same example as above using ConcurrentHashMap.

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class MapSynchro implements Runnable{
  private Map<String, String> testMap;
  public MapSynchro(Map<String, String> testMap){
    this.testMap = testMap;
  }

  public static void main(String[] args) {
    // Synchronized Map
    Map<String, String> testMap = new ConcurrentHashMap<String, String>();
    /// 4 threads
    Thread t1 = new Thread(new MapSynchro(testMap));
    Thread t2 = new Thread(new MapSynchro(testMap));
    Thread t3 = new Thread(new MapSynchro(testMap));
    Thread t4 = new Thread(new MapSynchro(testMap));
    
    t1.start();
    t2.start();
    t3.start();
    t4.start();
        
    try {
      t1.join();
      t2.join();
      t3.join();
      t4.join();
    } catch (InterruptedException e) {    
      e.printStackTrace();
    }
    System.out.println("Size of Map is " + testMap.size());
  }
  
  @Override
  public void run() {
    System.out.println("in run method" + Thread.currentThread().getName());
    String str = Thread.currentThread().getName();
    for(int i = 0; i < 5; i++){
      // adding thread name to make element unique
      testMap.put(str+i, str+i);
      try {
        // delay to verify thread interference
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}
Output
in run methodThread-2
in run methodThread-0
in run methodThread-3
in run methodThread-1
Size of Map is 20

That's all for the topic How to Synchronize Java HashMap. If something is missing or you have something to share about the topic please write a comment.


You may also like

Java Generics - Type Erasure

Using Java generics you can write generic programs and it also provide tighter type checks at compile time but these generics type remain only at source code level. When the source code is compiled all the generic type parameters are erased and this process is called type erasure in Java Generics.

How does Type erasure work

Type erasure in Java works as follows-

  1. Replace all type parameters in generic types with their bound type, if no explicit bound type is specified then replace generic type parameter with Object. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods with all the generic parameters replaced with actual types.
  2. Insert type casts if necessary to preserve type safety.
  3. Generate bridge methods to preserve polymorphism in extended generic types.

Type erasure in Generic class

Consider the following generic class with a generic type parameter T.

public class GenericClass<T> {
  T obj;
  GenericClass(T obj){
    this.obj = obj;
  }
  public T getObj() {
    return obj;
  } 
}

Because the type parameter T is unbounded, the Java compiler replaces it with Object and after compilation class looks like-

public class GenericClass {
  Object obj;
  GenericClass(Object obj){
    this.obj = obj;
  }
  public Object getObj() {
    return obj;
  } 
}

Consider another generic class with a bounded type parameter.

public class GenericClass<T extends String> {
  T obj;
  GenericClass(T obj){
    this.obj = obj;
  }
  public T getObj() {
    return obj;
  } 
}

Because the type parameter T is bounded, the Java compiler replaces it with the bound class String and after compilation class looks like-

public class GenericClass {
  String obj;
  GenericClass(String obj){
    this.obj = obj;
  }
  public String getObj() {
    return obj;
  } 
}

Type erasure in Generic method

The Java compiler also erases type parameters in generic method arguments. Consider the following generic method which counts the number of occurrences of passed element in the passed array.

public static <T> int count(T[] numberArray, T elem) {
  int cnt = 0;
  for (T e : numberArray){
    if (e.equals(elem))
      ++cnt;
  }
  return cnt;
}

Because T is unbounded, the Java compiler replaces it with Object and the compiled method looks like-

public static int count(Object[] numberArray, Object elem) {
  int cnt = 0;
  for (Object e : numberArray){
    if (e.equals(elem))
      ++cnt;
  }
  return cnt;
}

Type erasure and bridge methods

Sometimes, as part of the type erasure process compiler creates a synthetic method, called a bridge method. Consider the following classes to see an example of bridge method in Java.

public class GenClass<T> {
  T obj;
  public GenClass(T obj) { 
    this.obj = obj; 
  }
  public void setObj(T obj) {
    this.obj = obj;
  }  
}

This GenClass is then extended by another class as given below-

public class MyClass extends GenClass {
  public MyClass(Integer data) { 
    super(data); 
  } 
  public void setObj(Integer data) {
    System.out.println("MyClass.setData");
    super.setObj(data);
  } 
}

The intention here is to override the parent class setObj() method in the subclass. After type erasure, the GenClass and MyClass classes become-

public class GenClass {
  Object obj;
  public GenClass(Object obj) { 
    this.obj = obj; 
  }
  public void setObj(Object obj) {
    this.obj = obj;
  }  
}
public class MyClass extends GenClass {
  public MyClass(Integer data) { 
    super(data); 
  } 
  public void setObj(Integer data) {
    System.out.println("MyClass.setData");
    super.setObj(data);
  } 
}

After type erasure, the method signatures do not match. The GenClass method becomes setObj(Object obj) and the MyClass method becomes setObj(Integer data). Therefore, the GenClass setObj method does not override the MyClass setObj method.

To solve this problem and preserve the polymorphism of generic types after type erasure, Java compiler generates a bridge method to ensure that subtyping works as expected. For the MyClass class, the compiler generates the following bridge method for setObj().

public class MyClass extends GenClass {
  public MyClass(Integer data) { 
    super(data); 
  } 
  // Bridge method generated by the compiler
  public void setObj(Object data) {
    setObj((Integer) data);
  }
  public void setObj(Integer data) {
    System.out.println("MyClass.setData");
    super.setObj(data);
  } 
}

As you can see the bridge method has the same method signature as the GenClass’ setObj() method and it delegates to the original setObj() method.

That's all for the topic Java Generics - Type Erasure. If something is missing or you have something to share about the topic please write a comment.


You may also like
  • Java Generics - WildCards
  • Java Static Import With Examples
  • Java Externalizable Interface Example
  • Marker Interface in Java
  • Read Excel File in Java Using Apache POI
  • How to Sort ArrayList of Objects in Java
  • Spring @Conditional Annotation
  • Avro File Format in Hadoop
  • Java Generics - WildCards

    While writing generic code you can also use a question mark (?) as type which represents an unknown type and known as wildcard in Java generics.

    WildCard in Java generics and class relationship

    You can use wildcards to create a relationship between generic classes or interfaces.

    In case of non-generic classes

    class A { /* ... */ }
    class B extends A { /* ... */ }
    

    You can assign reference of child class to parent class.

    B b = new B();
    A a = b;
    

    But the same assignment does not apply to generic types.

    List<B> lb = new ArrayList<>();
    List<A> la = lb;   // compile-time error
    

    So, List<B> is not the subtype of List<A> even if A is the parent class.

    You can also understand it using the list of integers (List<Integer>) and list of numbers (List<Number>) where Number is the parent class of Integer but List<Integer> is not a subtype of List<Number> in fact, these two types are not related. The common parent of List<Number> and List<Integer> is List<?>. List of unknown type that could be a List<Integer>, List<A>, List<String> and so on.

    Using this knowledge of common parent of two generic classes we’ll see how to create a bounded relationship between two generic classes (or interfaces) using three types of wildcards.

    Types of wildcards in Java Generics

    Based on the limit you want to impose on the relationship between two generic classes there are three types of wildcards.

    • Upper bounded wildcards
    • Lower bounded wildcards
    • Unbounded wildcards

    Upper bounded wildcards

    To declare an upper-bounded wildcard, use the wildcard character ('?'), followed by the extends keyword, followed by the type that acts as upper bound. Upper bound wildcard matches the upper bound type or any of its subclasses.

    For example List<? extends Number> matches a list of type Number or any of its subclasses i.e. List<Integer>, List<Double>, List<Number>.

    Upper bounded wildcard Java example

    Suppose you want to write a method that can add all the elements of the passed list. Since you have to add the elements so List should have elements of type Integer, Float, Double since Number is the super class for all these wrapper classes so you can create an upper bound using Number class.

    import java.util.Arrays;
    import java.util.List;
    
    public class WildCard {
      public static void main(String[] args) {
        List<Integer> li = Arrays.asList(1, 2, 3, 4);
        System.out.println("sum = " + addListElements(li));
        //List<Double>
        List<Double> ld = Arrays.asList(1.1, 2.2, 3.3, 4.4);
        System.out.println("sum = " + addListElements(ld));
      }
        
      public static double addListElements(List<? extends Number> list){
        double s = 0.0;
        for (Number n : list) {
          s += n.doubleValue();
        }
        return s;
      }
    }
    
    Output
    sum = 10.0
    sum = 11.0
    

    Lower bounded wildcards

    A lower bounded wildcard is expressed using the wildcard character ('?'), following by the super keyword, followed by its lower bound. For example

    <? super A>

    A lower bounded wildcard restricts the unknown type to be a specific type or a super type of that type. For example you want to write a method that works on lists of Integer and the supertypes of Integer, such as Integer, Number, and Object then you would specify a lower bounded wildcard like this-

    List<? super Integer>

    Lower bounded wildcards Java example

    Suppose you want to write a method that can insert integers to the end of a list and that can be a List of Object, List of Number or List of Integer then you can create a lower bound using Integer class.

    import java.util.ArrayList;
    import java.util.List;
    
    public class WildCard {
      public static void main(String[] args) {
        // with List<Object>
        List<Object> lo = new ArrayList<Object>();
        insertNumbers(lo);
        
        // with List<Number>
        List<Number> ln = new ArrayList<Number>();
        insertNumbers(ln);
        
        // with List<Integer>
        List<Integer> li = new ArrayList<Integer>();
        insertNumbers(li);
      }
        
      public static void insertNumbers(List<? super Integer> list) {
        for (int i = 1; i <= 10; i++) {
          list.add(i);
        }
        System.out.println("Elements in List- " + list);
      }
    }
    
    Output
    Elements in List- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    Elements in List- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    Elements in List- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    

    Unbounded wildcards in Java generics

    The unbounded wildcard type is specified using the wildcard character (?).

    For example, List<?> represents a list of unknown type.

    Unbounded wildcard Java example

    Suppose you want to write a method that can print elements of a List of any type then you should use List<?> as method argument. Using List<Object> won’t work as List<Integer>, List<String>, List<Double> are not subtypes of List<Object>.

    import java.util.Arrays;
    import java.util.List;
    
    public class WildCard {
      public static void main(String[] args) {
        // With List<Integer>
        List<Integer> li = Arrays.asList(5, 6, 7);
        printListElements(li);
        // With List<Double>
        List<Double> ld = Arrays.asList(1.2, 3.8, 8.2);
        printListElements(ld);
      }
        
      public static void printListElements(List<?> list){
        for (Object e : list){
          System.out.print(e + " ");
        }
        System.out.println();
      }
    }
    
    Output
    5 6 7 
    1.2 3.8 8.2 
    
    That's all for the topic Java Generics - WildCards. If something is missing or you have something to share about the topic please write a comment.
    You may also like

    Java Generics - Bounded Type Parameters

    When you create a generic class or generic method the type parameters can be replaced by any class type but in some scenario you may want to restrict the types that can be used as type arguments in a parameterized type. That can be done using bounded type parameters in Java generics.

    Why bounded type parameter needed in Java Generics

    Let’s try to understand it with an example when you may need to use bounded parameters. For example, you have a generic class with a method that operates on numbers might only want to accept instances of Number or its subclasses.

    First let’s see what happens if you don’t use bounded type parameters. As an example we’ll have a generic class with a method average() that returns the average of an array of numbers. You have defined a generic class so that you can pass array of any type integer, double, float.

    public class BoundedType<T> {
      T[] numbers;
      BoundedType(T[] numbers){
        this.numbers = numbers;
      }
    
      public double average(){
        double sum = 0.0;
        for(int i = 0; i < numbers.length; i++){
          // Compile time error here
          sum += numbers[i].doubleValue();
        }
        double avg = sum/numbers.length;
        return avg;
      }
    }
    

    For calculating average suppose you have written a generic class as given above where you have used doubleValue() method to get number of type double for each number in the array. That should work well with any Number type as doubleValue() method is in Number class and it is the super class for all wrapper classes. But you will get compile time error at this line

    sum += numbers[i].doubleValue();

    Though your intention is to use this generic class always for numbers but there is no way for compiler to know that. For compiler BoundedType<T> means T can later be replaced by any type so there must be some mechanism for compiler to know that type parameter will be restricted to arguments of type Number. That’s where you use Bounded parameters in Java generics.

    How to declare bounded type parameters

    To declare a bounded type parameter, list the type parameter's name, followed by the extends keyword, followed by a super class (upper bound)

    <T extends parentclass>

    This specifies that T can only be replaced by parentclass, or any child class of parentclass. So, parentclass acts as an upper bound here.

    Bounded type parameter example

    If we take the same example as above then you can use Number as the upper bound for the type parameter to get rid of the compile time error. With that compiler knows that the type used for the type parameter is going to be a Number or any of its subclass.

    public class BoundedType<T extends Number> {
      T[] numbers;
      BoundedType(T[] numbers){
        this.numbers = numbers;
      }
      
      public double average(){
        double sum = 0.0;
        for(int i = 0; i < numbers.length; i++){
          // Compile time error here
          sum += numbers[i].doubleValue();
        }
        double avg = sum/numbers.length;
        return avg;
      }
      
      public static void main(String[] args) {
        Integer[] numArr = {3,4,5};
        BoundedType<Integer> obj = new BoundedType<Integer>(numArr);
        System.out.println("Average is: " + obj.average());
      }
    }
    

    Multiple Bounds in Java generics

    Type parameter can have multiple bounds too.

    <T extends A1 & A2 & A3>

    A type variable with multiple bounds is a subtype of all the types listed in the bound. Note that in case of multiple bounds only one of the bounds can be a class others have to be interfaces. If one of the bounds is a class, it must be specified first. For example:

    Class A { /* ... */ }
    interface B { /* ... */ }
    interface C { /* ... */ }
    
    class D <T extends A & B & C> { /* ... */ }
    

    Bounded type parameters with generic methods in Java

    In the above example bounded parameter is used at a class level but you can have generic methods with bounded type parameters too. Consider a scenario where you have a method to count the number of elements in an array greater than a specified element and you have written it as given below.

    public static <T> int countElements(T[] numbers, T element) {
      int count = 0;
      for (T e : numbers)
        if (e > element)  // compiler error
          ++count;
      return count;
    }
    

    You get compiler error at this line-

    if (e > element)

    because the greater than operator (>) applies only to primitive types such as short, int, double, long, float, byte, and char. You cannot use the > operator to compare objects.

    You will have to use a type parameter bounded by the Comparable<T> interface to compile the code.

    public static <T extends Comparable<T>> int countElements(T[] numbers, T element) {
      int count = 0;
      for (T e : numbers)
        if (e.compareTo(element) > 0)  // compiler error
          ++count;
      return count;
    }
    

    That's all for the topic Java Generics - Bounded Type Parameters. If something is missing or you have something to share about the topic please write a comment.


    You may also like

    Java CompletableFuture With Examples

    In this post we’ll learn about CompletableFuture class in Java along with examples to understand the functionalities this class provides.

    CompletableFuture in Java

    CompletableFuture is used for asynchronous computation of the task where the task is executed by a separate thread and the result is returned when it is ready.

    How is CompletableFuture different from Future

    You must be wondering there is already a Future interface doing the same job of asynchronous computation and returning a value then what does Java CompletableFuture has to offer.

    Future interface doesn’t provide a lot of features, in fact to get a result of asynchronous computation there is only future.get() method which is blocking so there is no scope for running multiple dependent tasks in a non-blocking fashion.

    That is where CompletableFuture with its rich API shines. It provides functionality to chain multiple dependent tasks which can be run asynchronously. So you can create a chain of tasks where the next task is triggered when the result of the current task is available.

    For example-
    CompletableFuture.supplyAsync(()->{return 4;})
    .thenApplyAsync(num-> Math.pow(num, 2))
    .thenAccept(num-> System.out.println("Value- " + num))
    .thenRun(()->System.out.println("Done"));

    Here first task returns a value, once the value is available next task does its computation and then the next task in the chain is executed.

    Another advantage of Java CompletableFuture is that it provides method to handle exceptions thrown in any of the dependent stages.

    CompletableFuture class in Java implements Future and CompletionStage interfaces. CompletableFuture class gets its behavior of running tasks as dependent stages by implementing CompletionStage interface.

    Important points about Java CompletableFuture

    1. CompletableFuture can be used as a Future that is explicitly completed or it can be used as a CompletionStage where completion of one stage triggers another dependent stage.
    2. CompletableFuture provides both async and non-async variants of a method.
    3. In case of a async method you can provide an Executor as an argument, in that case thread from the thread pool created using Executor is used for executing tasks. When async method without an Executor argument is used then the thread from the ForkJoinPool.commonPool() is used to execute tasks.

      For example consider the following three variants of thenApply() method-

      • thenApply(Function<? super T,? extends U> fn)- This one is non-async method.
      • thenApplyAsync(Function<? super T,? extends U> fn)- Asynchronous version, since executor is not passed as an argument so uses the default asynchronous execution facility (ForkJoinPool.commonPool()).
      • thenApplyAsync(Function<? super T,? extends U> fn, Executor executor)- Another asynchronous variant of thenApply() method, executed using the supplied Executor.

    CompletableFuture Java examples

    1- Simple example where a CompletableFuture instance is created using its constructor and the explicitly completed using the complete() method.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<String> cf = new CompletableFuture<>();
      cf.complete("CompletableFuture completed");
      System.out.println("Value- " + cf.get());
    }
    
    Output
    Value- CompletableFuture completed

    2- Using runAsync() method to execute an asynchronous task which returns a CompletableFuture<Void>.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<Void> cf = CompletableFuture.runAsync(()->{
        System.out.println("Running a runnable task");
      });
      System.out.println("Returned Value- " + cf.get());
    }
    Output
    Running a runnable task
    Returned Value- null

    3- As you can see from the previous example runAsync() method doesn’t return a result. If you want value to be returned then you can use supplyAsync() method.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<String> cf = CompletableFuture.supplyAsync(()->{
        System.out.println("Running a task");
        return "Task Completed";
      });
    
      System.out.println("Returned Value- " + cf.get());
    }
    Output
    Running a task
    Returned Value- Task Completed

    4- Till now we have seen examples with only one method, now let’s see some examples where chain of tasks is executed.

    static void cfExample() throws InterruptedException, ExecutionException {
      StringBuilder sb = new StringBuilder();
      CompletableFuture<String> cf = CompletableFuture.supplyAsync(()->{
        return "Completable";
      }).thenApply(s->sb.append(s).append("Future").toString());
      System.out.println("Returned Value- " + cf.get());
    }
    Output
    Returned Value- CompletableFuture

    In the example there are two stages-

    1. In first stage supplyAsync() method is executed which returns a result. When this stage completes normally it triggers the next stage.
    2. When the first stage completes, its result is then applied to the aptly named method thenApply().
    3. Since thenApply() method is used, which is non-async, so it will be executed by the same thread that executes the supplyAsync() method, it may also be executed by a thread that calls the supplyAsync() method (main thread).

    5- Using the asynchronous variant of the method.

    static void cfExample() throws InterruptedException, ExecutionException {
      StringBuilder sb = new StringBuilder();
      CompletableFuture<String> cf = CompletableFuture.supplyAsync(()->{
        return "Completable";
      }).thenApplyAsync(s->sb.append(s).append("Future").toString());
    
      System.out.println("Returned Value- " + cf.get());
    }

    It is same as the previous example, only difference is that it uses the async variant of the thenApply() method i.e. thenApplyAsync(). Now the chained task will be executed asynchronously using a separate thread obtained from ForkJoinPool.commonPool().

    6- You can supply an Executor with the asynchronous variant of the method.

    static void cfExample() throws InterruptedException, ExecutionException {
      ExecutorService executor = Executors.newFixedThreadPool(2);
      StringBuilder sb = new StringBuilder();
      CompletableFuture<String> cf = CompletableFuture.supplyAsync(()->{
        return "Completable";
      }).thenApplyAsync(s->sb.append(s).append("Future").toString(), executor);
    
      System.out.println("Returned Value- " + cf.get());
      executor.shutdown();
    }

    Now the chained task will be executed asynchronously using the passed executor and uses the separate thread obtained from the fixed thread pool.

    7- If you just want to consume the result of the previous stage with out returning any result you can use thenAccept() or thenRun() methods of the CompletableFuture class.

    In thenAccept method Consumer (a functional interface) is passed as parameter and it returns CompletionStage<Void>.

    In thenRun() method Runnable is passed as parameter and it returns CompletionStage<Void>.

    Though thenAccept() method can access the result of the task completed before it, thenRun() method doesn’t have access to the result of the task completed before it.

    static void cfExample() throws InterruptedException, ExecutionException {
      StringBuilder sb = new StringBuilder();
      CompletableFuture.supplyAsync(()->{return "Completable";})
        .thenApplyAsync(s->sb.append(s).append("Future").toString())
        .thenAccept(s->System.out.println("Current value is- " + s));
    }
    Output
    Current value is- CompletableFuture
    Using thenRun()
    static void cfExample() throws InterruptedException, ExecutionException {
      StringBuilder sb = new StringBuilder();
      CompletableFuture.supplyAsync(()->{return "Completable";})
        .thenApplyAsync(s->sb.append(s).append("Future").toString())
        .thenRun(()->System.out.println("Process completed"));
    }

    Using Java CompletableFuture’s thenCompose() method

    In CompletableFuture class there is another method thenCompose() where the computation performed by a stage can be expressed as a Function, another method which does the same is thenApply(). How these two methods thenCompose() and thenApply() differ is the how the value is returned.

    • thenApply() method returns a new CompletionStage with a type determined by the computation.
    • thenCompose() method returns a new CompletionStage with a type similar to the previous stage.

    Let’s try to clarify it with an example. Here we have two methods getValue() and getAnotherValue() both returning CompletableFuture<String>. First we’ll use thenApply() method.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<CompletableFuture<String>> cf = getValue().thenApply(s->getAnotherValue(s));
      System.out.println("Value- " + cf.get().get());
    }
    
    static CompletableFuture<String> getValue(){
      return CompletableFuture.supplyAsync(()->{return "Completable";});
    }
    
    static CompletableFuture<String> getAnotherValue(String str){
      return CompletableFuture.supplyAsync(()->{return str+"Future";});
    }

    If you see the chain here, there is a getValue() method which returns CompletableFuture<String> which is then used in the thenApply() method which again returns a result of type CompletableFuture<String> making it a nested structure of CompletableFuture<CompletableFuture<String>>.

    When you use thenCompose() method returned result has a type similar to the previous stage. That helps in flattening the nested structure.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<String> cf = getValue().thenCompose(s->getAnotherValue(s));
      System.out.println("Value- " + cf.get());
    }
    
    static CompletableFuture<String> getValue(){
      return CompletableFuture.supplyAsync(()->{return "Completable";});
    }
    
    static CompletableFuture<String> getAnotherValue(String str){
      return CompletableFuture.supplyAsync(()->{return str+"Future";});
    }

    Java CompletableFuture - Operations with more than one Completion stage

    1- Combining the result of two completion stages- You can combine two independent Completion stages using thenCombine() method which is executed with the results of two Completion stages as arguments to the supplied function.

    Here we have two methods getValue() and getAnotherValue() both returning CompletableFuture<String>. Once both of these Completion stages are completed, thenCombine() method is called with the results of both.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<String> cf = getValue().thenCombine(getAnotherValue(), (s1, s2)->s1+ " " +s2);
      System.out.println("Value- " + cf.get());
    }
    
    static CompletableFuture<String> getValue(){
      return CompletableFuture.supplyAsync(()->{return "Hello";});
    }
    
    static CompletableFuture<String> getAnotherValue(){
      return CompletableFuture.supplyAsync(()->{return "World";});
    }
    Output
    Value- Hello World

    2- Consuming the result of two completion stages- Just like thenAccept() method in Java CompletableFuture consumes the result of a completion stage there is also a thenAcceptBoth() method which consumes the result of two completion stages.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<Void> cf = getValue().thenAcceptBoth(getAnotherValue(), 
           (s1, s2)->System.out.println("Process completed with results- " +s1+ " " +s2));
      //System.out.println("Value- " + cf.get());
    }
    
    static CompletableFuture<String> getValue(){
      return CompletableFuture.supplyAsync(()->{return "Hello";});
    }
    
    static CompletableFuture<String> getAnotherValue(){
      return CompletableFuture.supplyAsync(()->{return "World";});
    }
    Output
    Process completed with results- Hello World

    3- Applying either of the two- If there are two CompletableFutures and only one of the stage completes normally and you want to apply the function on the result of that completion stage that completes normally then you can use applyToEither() method.

    In the example there are two methods getValue() and getAnotherValue(). In the getValue() method it is made to throw an exception and the method completes exceptionally. On the other hand getAnotherValue() method completes normally.

    static void cfExample() throws InterruptedException, ExecutionException {
      CompletableFuture<String> cf = getValue().applyToEitherAsync(getAnotherValue(), (s)->s.toUpperCase());
      System.out.println("Value- " + cf.get());
    }
    
    static CompletableFuture<String> getValue(){
      String str = null;
      return CompletableFuture.supplyAsync(() -> {
        if (str == null) {
          throw new IllegalArgumentException("Invalid String passed  " + str);
        }
        return str;
      }).exceptionally(exp -> {
        System.out.println("Exception message- " + exp.getMessage());
        return "";
      });
    }
    
    static CompletableFuture<String> getAnotherValue(){
      return CompletableFuture.supplyAsync(()->{return "World";});
    }
    Output
    Exception message-  java.lang.IllegalArgumentException: Invalid String passed null
    Value- WORLD

    As you can see applyToEitherAsync() method uses the result of the completion stage which completes normally.

    Exception handling in Java CompletableFuture

    For exception handling in Java CompletableFuture there are three methods-

    • handle
    • whenComplete
    • exceptionally

    handle and whenComplete methods are always executed whether an exception is thrown in the triggering stage or stage completes normally.

    Exceptionally method is executed only when the triggering stage completes exceptionally.

    Java CompletableFuture - Exception handling using exceptionally

    In the example String is passed as null causing an exception which results in exceptionally being called.

    static void cfExample() throws InterruptedException, ExecutionException {
      String str = null;
      CompletableFuture.supplyAsync(() -> {
        if (str == null) {
          throw new IllegalArgumentException("Invalid String passed " + str);
        }
        return str;
      }).exceptionally(exp -> {
          System.out.println("Exception message- " + exp.getMessage());
          return "";
      });
    }
    
    Output
    Exception message- java.lang.IllegalArgumentException: Invalid String passed null

    If there is no exception in the triggering stage exceptionally won’t be called.

    static void cfExample() throws InterruptedException, ExecutionException {
      String str = "Hello";
      CompletableFuture<String>cf = CompletableFuture.supplyAsync(() -> {
        if (str == null) {
          throw new IllegalArgumentException("Invalid String passed " + str);
        }
        return str;
      }).exceptionally(exp -> {
        System.out.println("Exception message- " + exp.getMessage());
        return "";
      });
      System.out.println("Value- " + cf.get());
    }
    Output
    Value- Hello

    Java CompletableFuture - Exception handling using handle

    handle() method is executed with this stage's result and exception as arguments to the supplied function. If no exception is thrown then exception argument would be null. Note that handle method is always executed whether exception is thrown or not, by checking exception argument for null it can be determined exception handling code is to be executed or not.

    static void cfExample() throws InterruptedException, ExecutionException {
      String str = null;
      CompletableFuture<String>cf = CompletableFuture.supplyAsync(() -> {
        if (str == null) {
          throw new IllegalArgumentException("Invalid String passed " + str);
        }
        return str;
      }).handle((s, e) -> {
        if(e != null) {
          System.out.println("Exception message- " + e.getMessage());
          s = "";
        }
        return s;
      });
      System.out.println("Value- " + cf.get());
    }
    Output
    Exception message- java.lang.IllegalArgumentException: Invalid String passed null
    Value-

    Java CompletableFuture - Exception handling using whenComplete

    Returns a new CompletionStage with the same result or exception as this stage so result can't be changed in the whenComplete method. Note that whenComplete method is always executed whether exception is thrown or not, by checking exception argument for null it can be determined exception handling code is to be executed or not.

    static void cfExample() throws InterruptedException, ExecutionException {
      String str = "Hello";
      CompletableFuture<String>cf = CompletableFuture.supplyAsync(() -> {
        if (str == null) {
          throw new IllegalArgumentException("Invalid String passed " + str);
        }
        return str;
      }).whenComplete((s, e) -> {
        System.out.println("In when complete method");
        if(e != null) {
          System.out.println("Exception message- " + e.getMessage());
        }
      });
      System.out.println("Value- " + cf.get());
    }
    Output
    In when complete method
    Value- Hello

    As you can see in the example exception is not thrown in the stage still whenComplete method is invoked but exception argument would be null in this case.

    That's all for the topic Java CompletableFuture With Examples. If something is missing or you have something to share about the topic please write a comment.


    You may also like