Code Pumpkin

Heap (Min/Max Heap)

March 31, 2017
Posted by Dipen Adroja


What is heap?

Heap is a balanced binary tree data strucure where the root-node key is compared with its children and arranged accordingly.

Max Heap: Root element will always be greater than or equal to either of its child element( see the image on left pane).

Min Heap: Root element will always be less than or equal to either of its child element.

Applications of Heap:

  • Implementing priority queue
  • When there is a need of always removing min/max element from the data strucure.


In this article, we will implement Max Heap, we will call it heap. Our heap data structure will support following operations:

Insert: To insert an element into the heap.

Delete: To delete an element from the heap.

FindMax: To find maximum element from th heap.

PrintHeap: To print the content of the heap.

We will implement the heap using the Array data structure. A complete binary tree can be uniquely represented by storing its level order traversal in an array.

The root is the second item in the array. We skip the index zero cell of the array for the convenience of implementation. Consider k-th element of the array, the

  • Its left child is located at 2*k index
  • Its right child is located at 2*k+1. index 
  • Its parent is located at k/2 index


Implementation of heap using array  is provided below:

import java.util.Arrays;
import java.util.NoSuchElementException;
  * MaxHeap implemented using Array
public class BinaryHeap {
    private static final int d= 2;
    private int[] heap;
    private int heapSize;
     * This will initialize our heap with default size.
    public BinaryHeap(int capacity){
        heapSize = 0;
        heap = new int[ capacity+1];
        Arrays.fill(heap, -1);
     *  This will check if the heap is empty or not
     *  Complexity: O(1)
    public boolean isEmpty(){
        return heapSize==0;
     *  This will check if the heap is full or not
     *  Complexity: O(1)
    public boolean isFull(){
        return heapSize == heap.length;
    private int parent(int i){
        return (i-1)/d;
    private int kthChild(int i,int k){
        return d*i  +k;
     *  This will insert new element in to heap
     *  Complexity: O(log N)
     *  As worst case scenario, we need to traverse till the root
    public void insert(int x){
            throw new NoSuchElementException("Heap is full, No space to insert new element");
        heap[heapSize++] = x;
     *  This will delete element at index x
     *  Complexity: O(log N)
    public int delete(int x){
            throw new NoSuchElementException("Heap is empty, No element to delete");
        int key = heap[x];
        heap[x] = heap[heapSize -1];
        return key;
     *  This method used to maintain the heap property while inserting an element.
    private void heapifyUp(int i) {
        int temp = heap[i];
        while(i>0 && temp > heap[parent(i)]){
            heap[i] = heap[parent(i)];
            i = parent(i);
        heap[i] = temp;
     *  This method used to maintain the heap property while deleting an element.
    private void heapifyDown(int i){
        int child;
        int temp = heap[i];
        while(kthChild(i, 1) < heapSize){
            child = maxChild(i);
            if(temp < heap[child]){
                heap[i] = heap[child];
            i = child;
        heap[i] = temp;
    private int maxChild(int i) {
        int leftChild = kthChild(i, 1);
        int rightChild = kthChild(i, 2);
        return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
     *  This method used to print all element of the heap
    public void printHeap()
            System.out.print("\nHeap = ");
            for (int i = 0; i < heapSize; i++)
                System.out.print(heap[i] +" ");
     *  This method returns the max element of the heap.
     *  complexity: O(1)
     public int findMax(){
             throw new NoSuchElementException("Heap is empty.");
         return heap[0];
     public static void main(String[] args){
         BinaryHeap maxHeap = new BinaryHeap(10);

Download Complete Java Program »

Main Heap Operations:

  • Insert: While inserting new element in the heap. We first insert it at the end of the heap. After that we will call the heapifyUp method to maintain the heap attribute. Which will make sure that the element placed at proper place by traversing the upwards.
  • Delete: Deleting an element from heap. We first remove element from the heap and then traverse down the heap using heapifyDown method to rearrange the attribute into the subsequent elements.
  • FindMax: This will simply returns the root element of the heap as it is a max heap. Root element will be the maximum element of the heap.

From the implementation we can see that, the largest element of the heap will always be at the root of the heap.

The same way you can also try to implement the Min Heap  structure.

That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.

Happy Learning 🙂

If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.

We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.

About the Author

Coder, Blogger, Wanderer, Philosopher, Curious pumpkin

Tags: , , , ,

Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
For more information on supported HTML tags in disqus comment, click here.
Total Posts : 124
follow us in feedly

Like Us On Facebook