+1 (315) 557-6473 

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


Instructions

Objective
Write a program that uses a binary tree and heap using Java programming language.

Requirements and Specifications

program that uses binary trees and heaps in Java programming language
program that uses binary trees and heaps in Java programming language 1
program that uses binary trees and heaps in Java programming language 2

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() ;

}