Question

1. Modify the HeapIntPriorityQueue class written in this chapter to make
it configurable in ways similar to Java's PriorityQueue class. Make it
possible for the heap to be a min-heap or max-heap. (If you create a
heap of objects, you could also modify it to accept a Comparator
parameter to its constructor.)

(add Comparator sort to provided Heap data structure Class)

2. Change to HeapPriorityQueue with CalendarDate which implements the Comparator interface

3. Modify HeapPriorityQueue to accept a different Comparator, like the one from Oracle, which has compare method to be used for deciding order in the Heap

Code to Test:

// 1. min heap
Queue pq = new PriorityQueue();
pq.add(42); pq.add(17); pq.add(9); pq.add(42);
pq.add(35); pq.add(-1); pq.add(88);
System.out.println(pq); // prints in array order
while (!pq.isEmpty()) { 
     System.out.print(pq.remove() + " "); // prints in Comparable order
}
System.out.println();

// 2. try some other Comparator:
HeapPriorityQueue pqDates = new HeapPriorityQueue(new CalendarDate());
pqDates.add(new CalendarDate(1,1,1942)); pqDates.add(new CalendarDate(1,2,1917)); 
pqDates.add(new CalendarDate(1,1,1909)); pqDates.add(new CalendarDate(1,1,1942));
System.out.println(pqDates); // prints in array order
while (!pqDates.isEmpty()) {
     System.out.print(pqDates.remove() + " "); // prints in Comparator order
}
System.out.println();

// 3. try a max heap of Integers
HeapPriorityQueue pqMax = new HeapPriorityQueue(Collections.reverseOrder());
pqMax.add(42); pqMax.add(17); pqMax.add(9); pqMax.add(42);
pqMax.add(35); pqMax.add(-1); pqMax.add(88);
System.out.println(pqMax); // prints in array order
while (!pqMax.isEmpty()) {
     System.out.print(pqMax.remove() + " "); // prints in Comparator order
}
System.out.println();

Code to Modify:

HeapPriorityQueue.java​​​​​​​

import java.util.*;

// Implements a priority queue of comparable objects using a

// min-heap represented as an array.

public class HeapPriorityQueue> {

private E[] elementData;

private int size;

// Constructs an empty queue.

@SuppressWarnings("unchecked")

public HeapPriorityQueue() {

elementData = (E[]) new Comparable[10];

size = 0;

}

// ADD METHODS HERE for exercise solutions:

// Adds the given element to this queue.

public void add(E value) {

// resize if necessary

if (size + 1 >= elementData.length) {

elementData = Arrays.copyOf(elementData, elementData.length * 2);

}

// insert as new rightmost leaf

elementData[size + 1] = value;

// "bubble up" toward root as necessary to fix ordering

int index = size + 1;

boolean found = false; // have we found the proper place yet?

while (!found && hasParent(index)) {

int parent = parent(index);

if (elementData[index].compareTo(elementData[parent]) < 0) {

swap(elementData, index, parent(index));

index = parent(index);

} else {

found = true; // found proper location; stop the loop

}

}

size++;

}

// Returns true if there are no elements in this queue.

public boolean isEmpty() {

return size == 0;

}

// Returns the minimum value in the queue without modifying the queue.

// If the queue is empty, throws a NoSuchElementException.

public E peek() {

if (isEmpty()) {

throw new NoSuchElementException();

}

return elementData[1];

}

// Removes and returns the minimum value in the queue.

// If the queue is empty, throws a NoSuchElementException.

public E remove() {

E result = peek();

// move rightmost leaf to become new root

elementData[1] = elementData[size];

size--;

// "bubble down" root as necessary to fix ordering

int index = 1;

boolean found = false; // have we found the proper place yet?

while (!found && hasLeftChild(index)) {

int left = leftChild(index);

int right = rightChild(index);

int child = left;

if (hasRightChild(index) &&

elementData[right].compareTo(elementData[left]) < 0) {

child = right;

}

if (elementData[index].compareTo(elementData[child]) > 0) {

swap(elementData, index, child);

index = child;

} else {

found = true; // found proper location; stop the loop

}

}

return result;

}

// Returns the number of elements in the queue.

public int size() {

return size;

}

// Returns a string representation of this queue, such as "[10, 20, 30]";

// The elements are not guaranteed to be listed in sorted order.

public String toString() {

String result = "[";

if (!isEmpty()) {

result += elementData[1];

for (int i = 2; i <= size; i++) {

result += ", " + elementData[i];

}

}

return result + "]";

}

// helpers for navigating indexes up/down the tree

private int parent(int index) {

return index / 2;

}

// returns index of left child of given index

private int leftChild(int index) {

return index * 2;

}

// returns index of right child of given index

private int rightChild(int index) {

return index * 2 + 1;

}

// returns true if the node at the given index has a parent (is not the root)

private boolean hasParent(int index) {

return index > 1;

}

// returns true if the node at the given index has a non-empty left child

private boolean hasLeftChild(int index) {

return leftChild(index) <= size;

}

// returns true if the node at the given index has a non-empty right child

private boolean hasRightChild(int index) {

return rightChild(index) <= size;

}

// switches the values at the two given indexes of the given array

private void swap(E[] a, int index1, int index2) {

E temp = a[index1];

a[index1] = a[index2];

a[index2] = temp;

}

}

CalendarDate.java

import java.util.Comparator;

// The CalendarDate class stores information about a single calendar date

// (upgraded from BJP text Chapter 10)

// similar code to www.buildingjavaprograms.com supplements

// added Comparator and year and hash code for later in course

public class CalendarDate implements Comparable,

Comparator {

// FIELDS

private int month;

private int day;

private int year;

// Constructors

public CalendarDate() {

// default 0,0 makes no sense, so using 1,1

this(1,1,1970); // zero epoch UNIX

}

public CalendarDate(int month, int day, int year) {

if (month<1 || month>12 || day<1 || day>31 || year<5 || year>9999 || year<0)

throw new IllegalArgumentException("Invalid month/day/year");

this.month = month;

this.day = day;

this.year = year;

}

// ACCESSORS (getters)

public int getMonth() {

return month;

}

public int getDay() {

return day;

}

public int getYear() {

return year;

}

// simple quick output

public String toString() {

return month + "/" + day + "/" + year;

}

// I thought a long date was dinner with a preson you don't like?

// But we'll also use the January 1, 1970 format instead

public String longDate() {

String[] names =

{"January","February","March","April","May","June","July","August","September","Oct

ober","November","December"};

return names[month-1] + " " + day + ", " + year;

}

// Compares this calendar date to another date.

// Dates are compared by month and then by day.

public int compareTo(CalendarDate other) {

if (this.year != other.year) {

return this.year - other.year;

} else if (this.month != other.month) {

return this.month - other.month;

} else {

return this.day - other.day;

}

}

// for Comparator interface

public int compare(CalendarDate first, CalendarDate second) {

// Should be the same as compareTo() result

return first.compareTo(second);

}

@Override

public boolean equals(Object other) {

// Note: must override equals(Object)

if (other instanceof CalendarDate) {

CalendarDate test = (CalendarDate)other;

return (this.compareTo(test)==0);

} else

return false;

}

@Override

public int hashCode() {

// days since 0/0/0 assuming 31 in each month

// number is strange, but works to achieve unique hash code

return (day+31*month+366*year);

}

}

Answer 1

Here is the modified code for HeapPriorityQueue class. I have created a variable to store the Comparator that will be comparing elements throughout the class. In the default constructor, this comparator is initialized to use default comparator (natural order) and a parameterized constructor is created accepting a Comparator argument, to support min-heap or max-heap based on the given comparator during run time.

Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// HeapPriorityQueue.java (modified)

import java.util.*;

// Implements a priority queue of comparable objects using a

// min-heap represented as an array.

public class HeapPriorityQueue<E extends Comparable<E>> {

      private E[] elementData;

      private int size;

      // comparator that is used to compare the elements

      private Comparator<E> comparator;

      // Constructs an empty queue.

      @SuppressWarnings("unchecked")

      public HeapPriorityQueue() {

            elementData = (E[]) new Comparable[10];

            size = 0;

            // initializing comparator to use default ordering

            comparator = new Comparator<E>() {

                  @Override

                  public int compare(E e1, E e2) {

                        return e1.compareTo(e2);

                  }

            };

      }

      // constructor taking a comparator argument

      @SuppressWarnings("unchecked")

      public HeapPriorityQueue(Comparator<E> comp) {

            elementData = (E[]) new Comparable[10];

            size = 0;

            // using comparator passed as parameter

            comparator = comp;

      }

      // ADD METHODS HERE for exercise solutions:

      // Adds the given element to this queue.

      public void add(E value) {

            // resize if necessary

            if (size + 1 >= elementData.length) {

                  elementData = Arrays.copyOf(elementData, elementData.length * 2);

            }

            // insert as new rightmost leaf

            elementData[size + 1] = value;

            // "bubble up" toward root as necessary to fix ordering

            int index = size + 1;

            boolean found = false; // have we found the proper place yet?

            while (!found && hasParent(index)) {

                  int parent = parent(index);

                  // comparing using comparator

                  if (comparator.compare(elementData[index], elementData[parent]) < 0) {

                        swap(elementData, index, parent(index));

                        index = parent(index);

                  } else {

                        found = true; // found proper location; stop the loop

                  }

            }

            size++;

      }

      // Returns true if there are no elements in this queue.

      public boolean isEmpty() {

            return size == 0;

      }

      // Returns the minimum value in the queue without modifying the queue.

      // If the queue is empty, throws a NoSuchElementException.

      public E peek() {

            if (isEmpty()) {

                  throw new NoSuchElementException();

            }

            return elementData[1];

      }

      // Removes and returns the minimum value in the queue.

      // If the queue is empty, throws a NoSuchElementException.

      public E remove() {

            E result = peek();

            // move rightmost leaf to become new root

            elementData[1] = elementData[size];

            size--;

            // "bubble down" root as necessary to fix ordering

            int index = 1;

            boolean found = false; // have we found the proper place yet?

            while (!found && hasLeftChild(index)) {

                  int left = leftChild(index);

                  int right = rightChild(index);

                  int child = left;

                  if (hasRightChild(index) &&

                  comparator.compare(elementData[right], elementData[left]) < 0) {

                        child = right;

                  }

                  if (comparator.compare(elementData[index], elementData[child]) > 0) {

                        swap(elementData, index, child);

                        index = child;

                  } else {

                        found = true; // found proper location; stop the loop

                  }

            }

            return result;

      }

      // Returns the number of elements in the queue.

      public int size() {

            return size;

      }

      // Returns a string representation of this queue, such as "[10, 20, 30]";

      // The elements are not guaranteed to be listed in sorted order.

      public String toString() {

            String result = "[";

            if (!isEmpty()) {

                  result += elementData[1];

                  for (int i = 2; i <= size; i++) {

                        result += ", " + elementData[i];

                  }

            }

            return result + "]";

      }

      // helpers for navigating indexes up/down the tree

      private int parent(int index) {

            return index / 2;

      }

      // returns index of left child of given index

      private int leftChild(int index) {

            return index * 2;

      }

      // returns index of right child of given index

      private int rightChild(int index) {

            return index * 2 + 1;

      }

      // returns true if the node at the given index has a parent (is not the

      // root)

      private boolean hasParent(int index) {

            return index > 1;

      }

      // returns true if the node at the given index has a non-empty left child

      private boolean hasLeftChild(int index) {

            return leftChild(index) <= size;

      }

      // returns true if the node at the given index has a non-empty right child

      private boolean hasRightChild(int index) {

            return rightChild(index) <= size;

      }

      // switches the values at the two given indexes of the given array

      private void swap(E[] a, int index1, int index2) {

            E temp = a[index1];

            a[index1] = a[index2];

            a[index2] = temp;

      }

}

/*OUTPUT (using provided test code)*/

[-1, 35, 9, 42, 42, 17, 88]

-1 9 17 35 42 42 88

[1/1/1909, 1/1/1942, 1/2/1917, 1/1/1942]

1/1/1909 1/2/1917 1/1/1942 1/1/1942

[88, 42, 42, 17, 35, -1, 9]

88 42 42 35 17 9 -1