Code Pumpkin

Heap (Min/Max Heap)

March 31, 2017
Posted by Pumpkin
Subscribe

maxHeap

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.

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

arrayHeap

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();
     }
}

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.

Happy Learning 🙂

Download Complete Java Program »

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";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank