How to Implement a Heap Data Structure in Java

Java Max heap, Min heap implementation with PriorityQueue

Originally Published in https://asyncq.com/

Introduction

Heap is a tree-based data structure and they are a complete binary tree.

There are generally two types of Heap:

• Max heap:
  In Max heap, the root should always be maximum compared to the left and right child, and this is true for all subtrees as well.

• Min heap:
  In Min heap, the root should always be minimum and it is the same for all subtrees as well

Use Cases

• When we need quick access to the highest or lowest element from N numbers of elements we can achieve it in the O(1) operation.
• Heap is optimized for operations such as Insert, Find Min/Max, and deletion operations compared to other data structures such as LinkedList and Array.
• Let’s consider one example where we have List of Jobs in the queue where each job has been assigned priority number.
• In this case we can always keep the…