Sorting

Min-heap priority queue

Pinterest LinkedIn Tumblr

Priority queue insert smallest key value is at the front of the queue (Min heap). Write a program to implement min heap priority queue.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
 
class DefaultComparator implements Comparator< Integer >
{
    @Override
    public int compare(Integer arg0, Integer arg1) {
        return arg0.compareTo(arg1);
    }
}
 
public class MinheapPriorityqueue extends AbstractCollection< Integer >
{
   
    private Comparator < Integer > myComp = new DefaultComparator();
    private int        mySize;
    private ArrayList < Integer >  myList;
 
     
    private class PQItr implements Iterator < Integer > {
        private int myCursor = 1;
        public Integer next() {
            return myList.get(myCursor);
        }
         
        public boolean hasNext() {
            return myCursor <= mySize;
        }
 
        public void remove(){
            throw new UnsupportedOperationException("remove not implemented");
        }
         
 
    }
 
   
    public MinheapPriorityqueue() {
        myList = new ArrayList< Integer >(32);
        myList.add(null);           
        mySize = 0;
    }
 
    public MinheapPriorityqueue(Comparator < Integer > comp) {
        this();
        myComp = comp;
    }
 
 
    public MinheapPriorityqueue(Collection < Integer > coll) {
        this();
        myList.addAll(coll);
        mySize = coll.size();
 
        for(int k=coll.size()/2; k >= 1; k--) {
            heapify(k);
        }
    }
 
     
     
    public boolean add(Integer o)  {
        myList.add(o);       
        mySize++;            
        int k = mySize;      
 
        while (k > 1 && myComp.compare(myList.get(k/2), o) > 0)  {
            myList.set(k, myList.get(k/2));
            k /= 2;
        }
        myList.set(k,o);
         
        return true;
    }
 
    public int size() {
        return mySize;
    }
 
    public boolean isEmpty() {
        return mySize == 0;
    }
 
   
    public Object remove() {
        if (! isEmpty())  {
            Object hold = myList.get(1);
             
            myList.set(1, myList.get(mySize)); 
            myList.remove(mySize);             
            mySize--;
            if (mySize > 1)  {
                heapify(1);
            }
            return hold;
        }
        return null;
    }
 
     
    public Object peek() {
        return myList.get(1);
    }
 
    
     
    public Iterator < Integer > iterator() {
        return new PQItr();
    }
 
   
     
    private void heapify(int vroot) {
        Integer last = myList.get(vroot);
        int child, k = vroot;
        while (2*k <= mySize) {
            child = 2*k;
            if (child < mySize &&
                        myComp.compare(myList.get(child),
                                       myList.get(child+1)) > 0) {
                child++;
            }
            if (myComp.compare((Integer) last, myList.get(child)) <= 0)  {
                break;
            } else {
                myList.set(k, myList.get(child));
                k = child;
            }
        }
        myList.set(k, last);
    }
    
 
    
     
    public static void main(String args[])
    {
        Integer []arr={34,56,23,88,67,89};
         
        MinheapPriorityqueue pq = new MinheapPriorityqueue(Arrays.asList(arr));
        System.out.println("List of items from array (Before sorting): "+ Arrays.toString(arr));
        System.out.print("List of items from Heap after sorting): [");
        while (pq.size() > 0)
        {
            if(pq.size()==1)
                System.out.print(pq.peek());
            else
                System.out.print(pq.peek() +",");
             
            pq.remove();
        }
        System.out.print("]\n");
    }
}

Output

List of items from array (Before sorting): [34, 56, 23, 88, 67, 89]
List of items from Heap after sorting): [23,34,56,67,88,89]

Algorithm Explanation

Insert items into a priority queue based on the priority.
The heap property is destroyed. Choose the 2 children of root and check which the minimum.
Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property.

Reference

  1. https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps
  2. https://en.wikipedia.org/wiki/Priority_queue

Write A Comment