Program That Uses a Binary Tree and Heap Using Java Programming Language Assignment Solution

Instructions

Objective

Write a Java assignment program that uses a binary tree and heap using.

Requirements and Specifications

Source Code

HEAP // // // The code for the class Heap. // // public methods: // insert (HeapElem newElement): insert a new element (with an integer key and a double data fields) to the heap // extractMax (): remove and return the data field of the heap element with maximum key // isEmpty(): return true if the heap is empty, false otherwise. // getSize(): return the number of elements in the heap // getMax(): return the data field of the heap element with the maximum key // preOrder(): print the heap elements (their key and data fields) in pre-order public class Heap implements PriorityQueueADT { private HeapElem[] heap; // the tree represented with an array private int size, maxSize; // the constructor for an originally empty heap public Heap(int newSize) { maxSize = newSize; heap = new HeapElem[maxSize]; size = 0; } // the constructor when the heap is initiated with an array a. The array is heapified by calling buildHeap. public Heap(HeapElem[] a) { heap = a; size = a.length; buildHeap(); } // from bottom to top, call reheapDown (bubble down). private void buildHeap() { // update this to call reheapDown a smaller number of times. if (size <= 1) { return; } int lastToCheck = (size - 2)/2; for (int i = lastToCheck - 1; i >= 0; i--) reheapDown(i); } // swap is called from reheapDown and reheapUp private void swap(int i, int j) { HeapElem temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } // bubble up the element at position index; called from insert private void reheapUp(int index) { int parent = (index + 1) / 2 - 1; if (index > 0 && heap[parent].key < heap[index].key) { swap(parent, index); reheapUp(parent); } } // bubble down the element at position index; called from insert private void reheapDown(int top) { int maxChild; int left = 2 * top + 1; int right = 2 * top + 2; if (left < size) { if (right >= size || heap[left].key > heap[right].key) maxChild = left; else maxChild = right; if (heap[top].key < heap[maxChild].key) { swap(top, maxChild); reheapDown(maxChild); } } } // insert; place the newKey in the last position, reheapUp, and update size public void insert(HeapElem newElement) { if (size < maxSize) { heap[size] = newElement; reheapUp(size); size++; } } // insert; place the newKey in the last position, reheapUp, and update size public void insert(int key, double data) { HeapElem newElement = new HeapElem(key, data); insert(newElement); } // remove and return the data field of the heap element with the maximum key public double extractMax() { HeapElem res = null; if (size > 0) { res = heap[0]; heap[0] = heap[--size]; reheapDown(0); } return res.data; } // return true if the heap is empty, false otherwise. public boolean isEmpty() { return size == 0; } // return the number of elements in the heap public int getSize() { // implement this. return size; } // return the data field of the heap element with the maximum key public double getMax() { // implement this. return heap[0].data; } // print the heap elements (their key and data fields) in pre-order public void preOrder() { if (size == 0) { return; } preorderStep(0); } private void preorderStep(int i) { heap[i].print(); if (2*i + 1 < size) { preorderStep(2*i + 1); if (2*i + 2 < size) { preorderStep(2*i + 2); } } } } PRIORITY QUEUE ADT // // This code declares the interface PriorityQueueADT including signatures and the public methods. public interface PriorityQueueADT { public void insert ( int key, double data ); public double extractMax() ; public double getMax() ; public boolean isEmpty() ; public int getSize() ; }