Question: The DatesHeapifier program You will write a program called DatesHeapifier consisting of only one method (function), the main. First, the program reads a list of
The DatesHeapifier program You will write a program called DatesHeapifier consisting of only one method (function), the main. First, the program reads a list of dates, in the format mm/dd/yyyy, from a text file whose name is entered as a command line Using a Binary Heap , inserts the dates into an initially empty heap and then performs a series of deletions to empty the heap. The program will then generate a list of the dates in the natural increasing order (+year+month+day) by displaying the dates as they are removed from the heap. The primary key is the year, secondary key is the month and tertiary key is the day and the keys are in ascending order for the first list. The list will be formatted as shown in Listing 1. Listing 1: Dates in +year+month+day Order Dates from < filename > in Ascending Order : < Day of the week > , < Month name > , < year > : : : : : : : : : : Second, the program again reads the dates from the same text file, inserts them into the empty heap and performs a series of deletions to empty the heap. The program will then generate a second list of the dates in the natural decreasing order (-year-month-day) by displaying the dates as they are removed from the heap. The primary key is the year, secondary key is the month and tertiary key is the day and the keys are in descending order for the second list. The list will be formatted as shown in Listing 2. Listing 2: Dates in -year-month-day Order Dates from < filename > in Descending Order : < Day of the week > , < Month name > , < year > : : : : : : : : : : Finally, the program again reads the dates from the same text file, inserts the corresponding 2019 dates for each date into the empty heap and performs a series of deletions to empty the heap. The program will then generate a third list of the dates in the natural increasing order (+month+day) by displaying the dates as they are removed from the heap. The primary key is the month and the secondary key is the day and the keys are in ascending order for the third list. Observe that you wont need a tertiary key since each date is in the same year (2019). The list will be formatted as shown in Listing 3. Using a Binary Heap #1 Listing 3: Dates in +month+day Order Dates from < filename > in Ascending Order and Weekday - in this Year : < Day of the week > , < Month name > : : : : : : : :
public class Heap
{
/**
* A complete tree stored in an array list representing this
* binary heap
*/
private ArrayList
/**
* A comparator lambda function that compares two elements of this
* heap when rebuilding it; cmp.compare(x,y) gives 1. negative when x less than y
* 2. positive when x greater than y 3. 0 when x equal y
*/
private Comparator cmp;
/**
* Constructs an empty heap using the compareTo method of its data type as the
* comparator
*/
public Heap()
{
tree = new Arraylist
}
/**
* A parameterized constructor that uses an externally defined comparator
* @param fn - a trichotomous integer value comparator function
*/
public Heap(Comparator fn)
{
//Implement method
}
public boolean isEmpty()
{
return tree.isEmpty();
}
public void insert(E obj)
{
{
tree.add(obj);
int place = size()-1;
int parent = (place-1)/2;
while(parent >= 0 && tree.get(place).compareTo(tree.get(parent)) > 0) {
swap(place, parent);
place = parent;
parent = (place - 1) / 2;
}
}
}
public E remove() throws HeapException
{
{
if(isEmpty())
throw new HeapException("Heap is empty");
E temp = tree.get(0);
tree.set(0,tree.get(size()-1));
tree.remove(size()-1);
reheapify(0,size());
return temp;
}
}
public E peek() throws HeapException
{
{
if(isEmpty())
throw new HeapException("Heap is empty");
return tree.get(0);
}
}
@Override
public int size()
{
return tree.size();
}
/**
* Swaps a parent and child elements of this heap at the specified indices
* @param place an index of the child element on this heap
* @param parent an index of the parent element on this heap
*/
private void swap(int place, int parent)
{
{
E temp = tree.get(place);
tree.set(place,tree.get(parent));
tree.set(parent,temp);
}
}
/**
* Rebuilds the heap to ensure that the heap property of the tree is preserved.
* @param root the root index of the sub-tree to be rebuilt
* @param eSize the size of the sub-tree to be rebuilt
*/
private void rebuild(int root, int eSize)
{
{
if(root > 1){
int child = 2*root+1;
if(2*root+2 < eSize-1){
if(tree.get(child+1).compareTo(tree.get(child)) > 0){
child = child + 1;
}
}
if(tree.get(root).compareTo(tree.get(child)) < 0){
swap(root,child);
reheapify(child,eSize);
}
}
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help