Applications of Heap:

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

Implementation:

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){
        if(isFull())
            throw new NoSuchElementException("Heap is full, No space to insert new element");
        heap[heapSize++] = x;
        heapifyUp(heapSize-1);
    }
     
    /**
     *  This will delete element at index x
     *  Complexity: O(log N)
     *
     */
    public int delete(int x){
        if(isEmpty())
            throw new NoSuchElementException("Heap is empty, No element to delete");
        int key = heap[x];
        heap[x] = heap[heapSize -1];
        heapSize--;
        heapifyDown(x);
        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];
            }else
                break;
             
            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] +" ");
            System.out.println();
        }
    /**
     *  This method returns the max element of the heap.
     *  complexity: O(1)
     */
     public int findMax(){
         if(isEmpty())
             throw new NoSuchElementException("Heap is empty.");
         return heap[0];
     }
      
     public static void main(String[] args){
         BinaryHeap maxHeap = new BinaryHeap(10);
         maxHeap.insert(10);
         maxHeap.insert(4);
         maxHeap.insert(9);
         maxHeap.insert(1);
         maxHeap.insert(7);
         maxHeap.insert(5);
         maxHeap.insert(3);
         maxHeap.printHeap();
         maxHeap.delete(5);
         maxHeap.printHeap();
     }
}

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.