How to implement a generic PriorityQueue with basic methods in java?

Question

I need to implement a custom priority queue without using the PriorityQueue form Java.Util... I have three basic methods : insert, remove and clear . All operations must be done in constant time O (log n). How can I accomplish this ? What algorithms should I use for these operations ? And lastly, what type of container should I use in which to keep the generic values ?

This is what I've done so far ...

public class PriorityQueue<E extends Comparable<? super E>> implements Comparable {
    private Stack<E> queue = new Stack<>();
    private int size;


    public PriorityQueue(int size) {
        this.size = size;
    }

    public PriorityQueue() {
        size = 50000;
    }

    public void insert(E value) {
        if (value == null) {
            throw new NullPointerException();
        }
        //how can I insert a value and what container should I use ?

    }

    public void remove() {
        //remove largest
    }

    public int compareTo(Object o) {
        if (o != null && o instanceof PriorityQueue) {
            PriorityQueue anotherQueue = (PriorityQueue) o;
            return this.size - anotherQueue.size;
        } else {
            throw new ClassCastException();
        }
    }
}

not much.. but help would be greatly appreciated !

Answer 1

I see your 'remove' operation takes the largest element. Seems like a 'Max Heap' would suit your purposes.

https://en.wikipedia.org/wiki/Heap_(data_structure)

Answer 2

Here I have used a maxHeap to put the elements in sorted order and this heap is implemented using an array.

max_size is the size of the array and size is the number of elements currently stored in the array.

• offer() - Insert the element at a leaf position and call shifUp() method.
• poll() - For this return the first element of the array. Then replace the first element of the array by one of its leaves. Then call shiftDown() method on the first element. The first element in the array will always be of highest priority.
• peek() - Here we just return the first element of the array. We don't remove it.

There are two more methods which I wasn't able to implement in case of generic array. Had it been an array of integers, there would have been no problem. These two methods are -

• remove(E e) - To delete an element from the queue. For this, I needed to change priority of e to infinity and then call shiftUp() method on e. After that, I just need to call the poll() method.

But I wasn't able to find how to change priority of a generic element to infinity. Had it been an integer, I would have just replaced the element in the backing array by Integer.MAX_VALUE.

• replace(E e1, E e2) - Here, I just need to remove the element e1 and insert element e2. Since this method calls remove() method, I wasn't able to implement it.

_

import java.util.Comparator;

public class PriorityQueueUsingHeap<E>
{

    private int size;

    private Object H[];

    public PriorityQueueUsingHeap(int max_size)
    {
        H = new Object[max_size];
    }

    private Comparator<E> comparator;

    public PriorityQueueUsingHeap(int max_size, Comparator<E> comparator)
    {
        this.comparator = comparator;
        H = new Object[max_size];
    }

    private E parent(int i)
    {
        return (E) H[(i - 1) / 2];
    }

    private E left(int i)
    {
        return (E) H[2 * i + 1];
    }

    private E right(int i)
    {
        return (E) H[2 * i + 2];
    }

    private boolean greaterThanOrEqualTo(E e1, E e2) // return e1>=e2
    {
        if (comparator != null)
        {
            return comparator.compare(e1, e2) >= 0;
        }

        else
        {
            return ((Comparable<E>) e1).compareTo(e2) >= 0;
        }
    }

    private boolean lessThan(E e1, E e2) // return e1<e2
    {
        if (comparator != null)
        {
            return comparator.compare(e1, e2) < 0;
        }

        else
        {
            return ((Comparable<E>) e1).compareTo(e2) < 0;
        }
    }

    private boolean lessThanOrEqualTo(E e1, E e2) // return e1<=e2
    {
        if (comparator != null)
        {
            return comparator.compare(e1, e2) <= 0;
        }

        else
        {
            return ((Comparable<E>) e1).compareTo(e2) <= 0;
        }
    }

    private boolean greaterThan(E e1, E e2) // return e1>e2
    {
        if (comparator != null)
        {
            return comparator.compare(e1, e2) > 0;
        }

        else
        {
            return ((Comparable<E>) e1).compareTo(e2) > 0;
        }
    }

    private void swap(int i1, int i2)
    {
        E temp = get(i1);
        H[i1] = H[i2];
        H[i2] = temp;
    }

    private E get(int i)
    {
        return (E) H[i];
    }

    private void shiftUp(int i)
    {
        while (i > 0 & greaterThanOrEqualTo(get(i), parent(i)))
        {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    private void shiftDown(int i)
    {
        int max_index = i;

        if ((2 * i + 1) <= size-1 && lessThan(get(max_index), left(i)))
            max_index = 2 * i + 1;

        if (((2 * i + 2) <= size-1) && (lessThan(get(max_index), right(i))))
            max_index = 2 * i + 2;

        if (i != max_index)
        {
            swap(i, max_index);
            shiftDown(max_index);
        }
    }

    public void offer(E data)
    {
        if(size == H.length)
            System.out.println("Queue is full");

        else
        {
            H[size] = (E) data;
            shiftUp(size);
            size++;
        }

    }

    public E peek()
    {
        return get(0);
    }

    public E poll()
    {
        if(size==0)
        {
            System.out.println("Queue is empty");
            return null;
        }
        else
        {
            E result = get(0);

            H[0] = H[size-1];
            size--;
            shiftDown(0);
            return result;
        }
    }

    public E remove(E e)
    {
        // Logic
        return e;
    }

    public void replace(E e1, E e2)
    {
        offer(e2);
        remove(e1);
    }

}

Here is main class for the same -

public class Main_PriorityQueueUsingHeap
{

    public static void main(String[] args)
    {

        PriorityQueueUsingHeap<Integer> q1 = new PriorityQueueUsingHeap<>(10);

        for (int i = 0; i < 5; i++)
        {
            q1.offer(i);
        }

        for (int i = 0; i < 5; i++)
        {
            System.out.print(q1.poll() + " ");
        }
        System.out.println();

        PriorityQueueUsingHeap<String> q2 = new PriorityQueueUsingHeap<>(10);

        q2.offer("Jatin");
        q2.offer("Ashvini");
        q2.offer("Ram");
        q2.offer("Mahesh");
        q2.offer("Kamal");

        for (int i = 0; i < 5; i++)
        {
            System.out.print(q2.poll() + " ");
        }
        System.out.println();

        PriorityQueueUsingHeap<String> q3 = new PriorityQueueUsingHeap<>(10, 
                (s1, s2) -> {
            return (s1.length() != s2.length()) ? s1.length() - s2.length() : s1.compareTo(s2);
        });

        q3.offer("Jatin");
        q3.offer("Ashvini");
        q3.offer("Ram");
        q3.offer("Mahesh");
        q3.offer("Kamal");

        for (int i = 0; i < 5; i++)
        {
            System.out.print(q3.poll() + " ");
        }
        System.out.println();

        PriorityQueueUsingHeap<Integer> q4 = new PriorityQueueUsingHeap<>(10);

        q4.offer(12);
        q4.offer(2);
        q4.offer(42);
        q4.offer(62);
        q4.offer(12);


        for (int i = 0; i < 5; i++)
        {
            System.out.print(q4.poll() + " ");
        }

    }

}

And here is the output -

4 3 2 1 0 
Ram Mahesh Kamal Jatin Ashvini 
Ashvini Mahesh Kamal Jatin Ram 
62 42 12 12 2 

Explanation for the main class - I have created 4 priority queues and did the following :

• q1 : Generic queue of Integers. Added integers 0 to 4 and then polled the elements one by one. Output shows that each of them came in decreasing order of their priority (Larger the number, higher is its priority).
• q2 : Generic queue of String with no comparator given. Hence two strings will be compared based on compareTo(E e) method present in Comparable interface. The output is sorted on the basis of lexicographical order.
• q3 : Generic queue of String with comparator. This comparator compares the length of two strings and if they are same, strings are sorted in lexicographical order.
• q4 : Generic queue of Integers. Added some random numbers and upon polling one by one, all came in decreasing order of their priority. Since no comparator is passed, the priority was decided on the basis of compareTo(E e) method.