This assignment gives you an opportunity to work on the heap data structure byimplementing an extended priority interface in Java. The interface is defined in agiven template code segment, with many of its methods already completed. Yourtask is to implement the remaining methods marked by TODO before their methodheadings. You should study the completed methods along with comments carefullybefore you complete the remaining methods. Note that Java is 0-based for array andlist indexes, instead of 1-based. If an arrayA[0..n1] of lengthnis used to implementa nearly complete tree for a heap, then the index for the parent of a child at indexjisbj1c/2, the index for the left child of a parent at indexjis 2j+ 1, and that forthe right child is 2j+ 2. In the template code segment, an instance of ArrayListis used as an array list for the heap, where indexes in this array list of lengthnare0,1, ..., n1. Note that if an element is removed from the heap, then an element isalso removed from this array list so that the length of this array list is always the sizeof the heap.

Need help with To Do sections.

/** * @author */

import java.util.List; import java.util.ArrayList; import java.util.NoSuchElementException;

interface ExtendedPriorityQueue { int size(); boolean isEmpty(); void add(E element);

// Returns a high-priority element without removing it. E getMin();

// Removes a high-priority element. E removeMin();

// Returns an element at the last nonleaf node in the heap E getLastInternal();

// Removes all elements at each leaf node in the heap void trimEveryLeaf();

// Shows the heap as a binary tree in plain text void showHeap(); }

public class Heap> implements ExtendedPriorityQueue { private static final int INIT_CAP = 10; // A default size of list private ArrayList list; // used as an array to keep the elements in the heap // list.size() returns the number of elements in the list, // which is also the size of the heap. // For 0 <= k < list.size(), list.get(k) returns the element at position k of list // list.remove( list.size() - 1 ) removes the last element from the list; // note that there is no need to remove any element before the last element.

public Heap() { list = new ArrayList(INIT_CAP); }

public Heap(int aSize) { if ( aSize < 1 ) throw new IllegalStateException(); list = new ArrayList(aSize); }

// Builds a heap from a list of elements. public Heap(List aList) { int j, k; int len = aList.size(); if ( len < 1 ) throw new IllegalArgumentException(); list = new ArrayList(len); for ( E t : aList ) list.add(t); if ( len < 2 ) return; j = (len - 2) / 2; // j is the largest index of an internal node with a child. for ( k = j; k >= 0; k-- ) percolateDown(k); } // O(n) time

public int size() { return list.size(); }

public boolean isEmpty() { return list.isEmpty(); }

public void add(E element) { if ( element == null ) throw new NullPointerException("add"); list.add(element); // append it to the end of the list percolateUp(); // move it up to the proper place }

// TODO: O(log n) // Moves the last element up to the proper place so that the heap property holds. private void percolateUp() { }

// Swaps the elements at the parent and child indexes. private void swap(int parent, int child) { E tmp = list.get(parent); list.set( parent, list.get(child) ); list.set(child, tmp); }

public E getMin() { if ( list.isEmpty() ) throw new NoSuchElementException(); return list.get(0); }

// TODO: O(1) // Returns an element at the last nonleaf node in the heap // If the size of the heap is less than 2, it throws new NoSuchElementException(). public E getLastInternal() { }

public E removeMin() { if ( list.isEmpty() ) throw new NoSuchElementException(); E minElem = list.get(0); // get the min element at the root list.set(0, list.get(list.size() - 1) ); // copy the last element to the root list.remove( list.size() - 1 ); // remove the last element from the list if ( ! list.isEmpty() ) percolateDown(0); // move the element at the root down to the proper place return minElem; }

// TODO: O(n) // If the heap contains internal (nonleaf) nodes, trim every leaf element. // If the size of the heap is less than 2, it throws new NoSuchElementException(). public void trimEveryLeaf() { }

// TODO: O(log n) // Move the element at index start down to the proper place so that the heap property holds. private void percolateDown(int start) { if ( start < 0 || start >= list.size() ) throw new RuntimeException("start < 0 or >= n"); }

// Shows the tree used to implement the heap with the root element at the leftmost column // and with 'null' indicating no left or right child. // This method is used to help check if the heap is correctly constructed. public void showHeap() { if ( list.isEmpty() ) return; recShowHeap(0, ">"); }

public void recShowHeap(Integer r, String level) { int len = list.size(); if ( r >= len ) { System.out.println(level + "null"); return; } System.out.println(level + list.get(r) ); // get the min element at the root recShowHeap(2 * r + 1, " " + level); recShowHeap(2 * r + 2, " " + level); }

// This method repeatedly removes the smallest element in the heap and add it to the list. public static > void heapSort(List aList) { if ( aList.isEmpty() ) return; Heap aHeap = new Heap(aList); aList.clear(); while ( ! aHeap.isEmpty() ) aList.add( aHeap.removeMin() ); } } // Heap

/** * @author ** */

import java.util.List; import java.util.ArrayList;

public class Application {

public static void main(String[] args) { Heap pq = new Heap(); pq.add(10); pq.add(15); pq.add(20); pq.add(30); pq.add(25); pq.add(25); pq.add(30); pq.add(40); pq.add(35); pq.add(50); pq.add(10); pq.showHeap(); System.out.println( pq.getLastInternal() ); pq.trimEveryLeaf(); pq.showHeap(); while ( ! pq.isEmpty() ) { System.out.println( pq.removeMin() ); }

List alist = new ArrayList(); alist.add("TGA"); alist.add("ACG"); alist.add("GCT"); alist.add("GTA"); System.out.println( "Before sorting: " + alist.toString() ); Heap.heapSort(alist); System.out.println( "After sorting: " + alist.toString() ); } }