Answers for "min heap"

min heap stl

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

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

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 of a min heap

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

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

min heap insertion

Williams Algorithm: top downwhile not end of array, 	if heap is empty, 		place item at root; 	else, 		place item at bottom of heap; 		while (child > parent) 			swap(parent, child); 	go to next array element; end