min heap code example

Example 1: min heap in c++

priority_queue <int, vector<int>, greater<int>> minHeap;

Example 2: min max heap java

// min heap: PriorityQueue implementation from the JDK
PriorityQueue<Integer> prq = new PriorityQueue<>();

// max heap: PriorityQueue implementation WITH CUSTOM COMPARATOR PASSED
// Method 1: Using Collections (recommended)
PriorityQueue<Integer> prq = new PriorityQueue<>(Collections.reverseOrder());
// Method 2: Using Lambda function (may cause Integer Overflow)
PriorityQueue<Integer> prq = new PriorityQueue<>((a, b) -> b - a);

Example 3: heaps in java

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

Example 4: max heap c++

#include <iostream>
using namespace std;
void max_heap(int *a, int m, int n) {
   int j, t;
   t = a[m];
   j = 2 * m;
   while (j <= n) {
      if (j < n && a[j+1] > a[j])
         j = j + 1;
      if (t > a[j])
         break;
      else if (t <= a[j]) {
         a[j / 2] = a[j];
         j = 2 * j;
      }
   }
   a[j/2] = t;
   return;
}
void build_maxheap(int *a,int n) {
   int k;
   for(k = n/2; k >= 1; k--) {
      max_heap(a,k,n);
   }
}
int main() {
   int n, i;
   cout<<"enter no of elements of array\n";
   cin>>n;
   int a[30];
   for (i = 1; i <= n; i++) {
      cout<<"enter elements"<<" "<<(i)<<endl;
      cin>>a[i];
   }
   build_maxheap(a,n);
   cout<<"Max Heap\n";
   for (i = 1; i <= n; i++) {
      cout<<a[i]<<endl;
   }
}

Example 5: heap sort heapify and max heap in binary tree

Implementation of heap sort in C:

#include <stdio.h>
int main()
{
   int heap[10], array_size, i, j, c, root, temporary;
   printf("\n Enter size of array to be sorted :");
   scanf("%d", &array_size);
   printf("\n Enter the elements of array : ");
   for (i = 0; i < array_size; i++)
      scanf("%d", &heap[i]);
   for (i = 1; i < array_size; i++)
   {
       c = i;
       do
       {
           root = (c - 1) / 2;            
           if (heap[root] < heap[c])   /* to create MAX heap array */
           {                                  // if child is greater than parent swap them
               temporary = heap[root];      // as structure is of complete binary tree
               heap[root] = heap[c];     // it took logn steps to reach from root to leaf
               heap[c] = temporary;
           }
           c = root;
       } while (c != 0);
   }
   printf("Heap array : ");
   for (i = 0; i < array_size; i++)
       printf("%d\t ", heap[i]);         //printing the heap array
   for (j = array_size - 1; j >= 0; j--)
   {
       temporary = heap[0];
       heap[0] = heap[j] ;   /* swap max element with rightmost leaf element */
       heap[j] = temporary;
       root = 0;
       do
       {
           c = 2 * root + 1;    /* left node of root element */
           if ((heap[c] < heap[c + 1]) && c < j-1)
               c++;
           if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */
           {
               temporary = heap[root];
               heap[root] = heap[c];
               heap[c] = temporary;
           }
           root = c;
       } while (c < j);
   }
   printf("\n The sorted array is : ");
   for (i = 0; i < array_size; i++)
      printf("\t %d", heap[i]);
}

Example 6: example of a min heap

10                      10
         /      \               /       \  
       20        100          15         30  
      /                      /  \        /  \
    30                     40    50    100   40