Question

In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to implement your own flexible priority queue ADT using both min- and max-heap in Java. The specifications of the flexible priority queue are provided in the following. The heap(s) must be implemented from scratch using an array that is automatically extendable. You are not allowed to use any list (including arraylist), tree, vector, or heap implementation already available in Java. You must not duplicate code for implementing min- and max-heaps (i.e. the same code must he used for constructing min or max heaps. Hence think of a flexible way to parameterize your code for either min - or max heap). The following are the access methods of the flexible priority queue ADT: remove(): removes and returns the entry (a key, value pair) with the smallest or biggest key depending on the current state of the priority queue (either Min or Max). insert (k, v): Insert the (k, v) entry which is a key(k). value(v) pair to the priority queue. top(): returns the top entry (with the minimum or the maximum key depending on whether it is a Min- or Max-priority queue, without removing the entry. toggle() transforms a min- to a max-priority queue or vice versa. switchToMin(): transforms a max- to a min-priority queue: else leave unchanged. switchToMax(): transforms a min- to a max-priority queue; else leave unchanged, stale (): returns the current state (Min or Max) of the priority queue. isEmpty(): returns true if the priority queue is empty. size(): returns the current number of entries in the priority queue. You have to submit the following deliverables: a) Pseudo code of your implementation of the flexible priority queue ADT using a parameterized heap that is implemented using extendable array. Note that Java code will not be considered as pseudo code. Your pseudo code must be on a higher and more abstract level. b) Tight big-Oh time complexities of toggle(), switchToMin(), and switchToMax() operations, together with your explanations. c) Well documented Java source code with 20 different but representative examples demonstrating the functionality of your implemented ADT. These examples should demonstrate all cases of your ADT functionality (e.g.. all operations of your ADT, several cases requiring automatic array extension, sufficient number of down and up-heap operations).

Answer 1

Complete Program:

File: Entry.java

// Entry class implementation
public class Entry<K extends Comparable<K>, V extends Comparable<V>>
{  
   // data fields
   private K key;
   private V value;
  
   // default constructor implementation
   public Entry()
   {
       this(null, null);
   }
  
   // parameterized constructor implementation
   public Entry(K k, V v)
   {
       key = k;
       value = v;
   }
  
   // getKey method implementation
   public K getKey()
   {
       return key;
   }
  
   // getValue method implementation
   public V getValue()
   {
       return value;
   }
  
   // setKey method implementation
   public void setKey(K k)
   {
       key = k;
   }
  
   // setValue method implementation
   public void setValue(V v)
   {
       value = v;
   }
  
   // toString method implementation
   public String toString()
   {
       return "(" + key + ", " + value + ")";
   }
} // end of Entry class

File: FlexiblePriorityQueue.java

// FlexiblePriorityQueue class implementation
public class FlexiblePriorityQueue<K extends Comparable<K>, V extends Comparable<V>>
{
   // data fields
   private Entry<K, V>[] heap;
   private int numberOfEntries;
   private String currentState;
   private final String MIN_HEAP = "Min Heap";
   private final String MAX_HEAP = "Max Heap";

   // default constructor implementation
   @SuppressWarnings("unchecked")
   public FlexiblePriorityQueue()
   {
       heap = (Entry<K, V>[])new Entry[0];
       numberOfEntries = 0;      
       currentState = MIN_HEAP;
   } // end of default constructor

   // insert (k, v): Insert the (k, v) entry which is a key(k), value(v) pair to the priority queue.
   @SuppressWarnings("unchecked")
   public void insert(K k, V v)
   {      
       Entry<K, V>[] tempHeap = (Entry<K, V>[])new Entry[numberOfEntries + 1];
      
       for(int i = 0; i < numberOfEntries; i++)
       {
           tempHeap[i] = heap[i];
       }      
       heap = tempHeap;
      
       int count = numberOfEntries;
       int parent = (int) Math.floor((count - 1) / 2);
      
       if(currentState.equalsIgnoreCase(MIN_HEAP))
       {
           while(count > 0 && k.compareTo(heap[parent].getKey()) < 0)
           {
               heap[count] = heap[parent];
               count = parent;
               parent = (int) Math.floor((count - 1) / 2);
           }
       }
      
       if(currentState.equalsIgnoreCase(MAX_HEAP))
       {
           while(count > 0 && k.compareTo(heap[parent].getKey()) > 0)
           {
               heap[count] = heap[parent];
               count = parent;
               parent = (int) Math.floor((count - 1) / 2);
           }
       }
      
       heap[count] = new Entry<K, V>(k, v);;
       numberOfEntries++;
   } // end of insert method
  
   // remove(): removes and returns the entry (a key, value pair) with the smallest or biggest key depending on the current state of the priority queue (either Min or Max).
   public Entry<K, V> remove()
   {
       if(isEmpty())
           return null;

       Entry<K, V> topEntry = heap[0];
       heap[0] = heap[numberOfEntries - 1];
       numberOfEntries--;
       heapify(0);
      
       return topEntry;
   } // end of remove method
      
   // top(): returns the top entry (with the minimum or the maximum key depending on whether it is a Min- or Max-priority queue, without removing the entry.
   public Entry<K, V> top()
   {
       if(numberOfEntries == 0)
           return null;
       else
           return heap[0];
   } // end of top method

   // toggle() transforms a min- to a max-priority queue or vice versa.
   public void toggle()
   {
       if(currentState.equalsIgnoreCase(MIN_HEAP))
           currentState = MAX_HEAP;
       else
           currentState = MIN_HEAP;

       rebuildHeap();
   } // end of toggle method

   // switchToMin(): transforms a max- to a min-priority queue: else leave unchanged.
   public void switchToMin()
   {
       if(currentState.equalsIgnoreCase(MAX_HEAP))
       {
           currentState = MIN_HEAP;
           rebuildHeap();
       }
   } // end of switchToMin method

   // switchToMax(): transforms a min- to a max-priority queue; else leave unchanged.
   public void switchToMax()
   {
       if(currentState.equalsIgnoreCase(MIN_HEAP))
       {
           currentState = MAX_HEAP;
           rebuildHeap();
       }
   } // end of switchToMax method

   // stale (): returns the current state (Min or Max) of the priority queue.
   public String state()
   {
       return currentState;
   } // end of state method
  
   // isEmpty(): returns true if the priority queue is empty.
   public boolean isEmpty()
   {
       return numberOfEntries == 0;
   } // end of isEmpty method

   // size(): returns the current number of entries in the priority queue.
   public int size()
   {
       return numberOfEntries;
   } // end of size method
  
   // toString method implementation
   public String toString()
   {
       StringBuilder sb = new StringBuilder();
       sb.append("[");
       for(int i = 0; i < numberOfEntries; i++)
       {
           sb.append(heap[i]);  
          
           if(i < numberOfEntries - 1)
               sb.append(", ");
       }
       sb.append("]" );
      
       return sb.toString();
   } // end of toString method
      
   // rebuildHeap method implementation
   private void rebuildHeap()
   {
       for(int i = numberOfEntries / 2 - 1; i >= 0; i--)
       {
           heapify(i);
       }
   } // end of rebuildHeap method
  
   // heapify method implementation
   private void heapify(int index)
   {
       int current = index;
       int left = 2 * index + 1;
       int right = 2 * index + 2;

       if(currentState.equalsIgnoreCase(MIN_HEAP))
       {
           if(left < numberOfEntries && heap[index].getKey().compareTo(heap[left].getKey()) > 0)
           {
               current = left;
           }
          
           if(right < numberOfEntries && heap[current].getKey().compareTo(heap[right].getKey()) > 0)
           {
               current = right;
           }

       }      
      
       if(currentState.equalsIgnoreCase(MAX_HEAP))
       {
           if(left < numberOfEntries && heap[index].getKey().compareTo(heap[left].getKey()) < 0)
           {
               current = left;
           }
          
           if(right < numberOfEntries && heap[current].getKey().compareTo(heap[right].getKey()) < 0)
           {
               current = right;
           }
       }

       if(current != index)
       {          
           Entry<K, V> tempEntry = heap[index];
           heap[index] = heap[current];
           heap[current] = tempEntry;
          
           heapify(current);
       }
   } // end of heapify method  
} // end of FlexiblePriorityQueue class

File: FlexiblePriorityQueueTest.java

// FlexiblePriorityQueueTest class implementation
public class FlexiblePriorityQueueTest
{
   // start main method
   public static void main(String[] args)
   {
       FlexiblePriorityQueue<String, Integer> fpq = new FlexiblePriorityQueue<String, Integer>();
      
       fpq.insert("true", 1);
       fpq.insert("your", 2);
       fpq.insert("other", 3);
       fpq.insert("has", 4);
       fpq.insert("the", 5);
       fpq.insert("code", 6);
       fpq.insert("are", 7);
       fpq.insert("vice", 8);
       fpq.insert("versa", 9);
      
       System.out.println("Current State: " + fpq.state());      
       System.out.println("Entries: " + fpq);  
      
       System.out.println("\nRemoved top element: " + fpq.remove());
       System.out.println("Entries: " + fpq);
      
       System.out.println("\nToggling the state...");
       fpq.toggle();  
      
       System.out.println("\nCurrent State: " + fpq.state());      
       System.out.println("Entries: " + fpq);
      
       System.out.println("\nRemoved top element: " + fpq.remove());
       System.out.println("Entries: " + fpq);
   } // end of main method
} // end of FlexiblePriorityQueueTest class

Sample Output:

Current State: Min Heap Entries (are, 7),(other, 3), (code, 6),(versa, 9), (the, 5),(true, 1), (has, 4 (your, 2),(vice, 8)1 Removed top element: (are, 7) Entries: (code, 6),(other, 3), (has, 4) (versa, 9),(the, 5), (true, 1), (vice, 8), (your, 2) Toggling the state. . . Current State: Entries: [ (your, 2), (versa, 9), (vice, 8),(other, 3), (th, 5),(true, 1), (has, 4), (code, 6) Removed top element: (your, 2) Entries: [ (vice, 8), (versa, 9), (true, 1), (other, 3), (th5), (code, 6), (has, 4) Max Heap