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

1 Comment

  1. With havin so much written content do you ever run into any problems of plagorism or copyright violation? My blog has a lot of unique content I’ve either written myself or outsourced but it seems a lot of it is popping it up all over the internet without my authorization. Do you know any techniques to help protect against content from being stolen? I’d certainly appreciate it.

Write A Comment