ZuoTi.Pro
Question
add/ remove any methods to the program. please post new code and output
Min Heap: public class MinHeap private int[] Heap; private int size; private int maxsize; private static final int FRONT = 1;
private void swap(int fpos, int spos) int tmp; tmp = Heap[fpos); Heap[fpos] = Heap[spos]; Heap[spos] = tmp; private void minH
public void print) for (int i = 1; i <=size / 2; i++) System.out.print(PARENT : + Heap[i] + LEFT CHILD: + Heap[2] + RIGH
minHeap.insert(22); minHeap.insert(9); minHeap.min Heap(); minHeap.print(); System.out.println(The Min val is + minHeap.re

Min Heap:
public class MinHeap {
private int[] Heap; private int size; private int maxsize;
private static final int FRONT = 1;
public MinHeap(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1]; Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos) {
return pos / 2; }
private int leftChild(int pos) {
return (2 * pos); }
private int rightChild(int pos) {
return (2 * pos) + 1; }
private boolean isLeaf(int pos) {
if (pos >= (size / 2) && pos <= size) {
return true; }
return false;

}
private void swap(int fpos, int spos) {
int tmp;
tmp = Heap[fpos]; Heap[fpos] = Heap[spos]; Heap[spos] = tmp;
}
private void minHeapify(int pos) {
if (!isLeaf(pos)) {
if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)])
{
if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
minHeapify(leftChild(pos)); }else
{
swap(pos, rightChild(pos)); minHeapify(rightChild(pos));
} }
} }
public void insert(int element) {
Heap[++size] = element; int current = size;
while (Heap[current] < Heap[parent(current)]) {
swap(current,parent(current));
current = parent(current); }

}
public void print() {
for (int i = 1; i <= size / 2; i++ ) {
System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]); System.out.println();
} }
public void minHeap() {
for (int pos = (size / 2); pos >= 1 ; pos--) {
minHeapify(pos); }
}
public int remove() {
int popped = Heap[FRONT]; Heap[FRONT] = Heap[size--]; minHeapify(FRONT);
return popped;
}
public static void main(String...arg) {
System.out.println("The Min Heap is "); MinHeap minHeap = new MinHeap(15); minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17); minHeap.insert(10); minHeap.insert(84); minHeap.insert(19); minHeap.insert(6);

minHeap.insert(22); minHeap.insert(9); minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.remove()); }
}
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

    public class MinHeap

    {

        private int[] Heap;

        private int size;

        private int maxsize;

   

        private static final int FRONT = 1;

   

        public MinHeap(int maxsize)

        {

            this.maxsize = maxsize;

            this.size = 0;

            Heap = new int[this.maxsize + 1];

            Heap[0] = Integer.MIN_VALUE;

        }

   

        private int parent(int pos)

        {

            return pos / 2;

        }

   

        private int leftChild(int pos)

        {

            return (2 * pos);

        }

   

        private int rightChild(int pos)

        {

            return (2 * pos) + 1;

        }

   

        private boolean isLeaf(int pos)

        {

            if (pos >= (size / 2) && pos <= size)

            {

                return true;

            }

            return false;

        }

   

        private void swap(int fpos, int spos)

        {

            int tmp;

            tmp = Heap[fpos];

            Heap[fpos] = Heap[spos];

            Heap[spos] = tmp;

        }

   

        private void minHeapify(int pos)

        {

            if (!isLeaf(pos))

            {

                if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)])

                {

                    if (Heap[leftChild(pos)] < Heap[rightChild(pos)])

                    {

                        swap(pos, leftChild(pos));

                        minHeapify(leftChild(pos));

                    }else

                    {

                        swap(pos, rightChild(pos));

                        minHeapify(rightChild(pos));

                    }

                }

            }

        }

   

        public void insert(int element)

        {

            Heap[++size] = element;

            int current = size;

   

            while (Heap[current] < Heap[parent(current)])

            {

                swap(current,parent(current));

                current = parent(current);

            }  

        }

   

        public void print()

        {

            for (int i = 1; i <= size / 2; i++ )

            {

                System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]

                    + " RIGHT CHILD :" + Heap[2 * i + 1]);

                System.out.println();

            }

        }

   

      

   

      

   

        public static void main(String...arg)

        {

            System.out.println("The Min Heap is ");

            MinHeap minHeap = new MinHeap(15);

            minHeap.insert(5);

            minHeap.insert(3);

            minHeap.insert(17);

            minHeap.insert(10);

            minHeap.insert(84);

            minHeap.insert(19);

            minHeap.insert(6);

            minHeap.insert(22);

            minHeap.insert(9);


   

            minHeap.print();

          

        }

    }

Output :-

$javac MinHeap.java $java -Xmx128M - Xms 16M MinHeap The Min Heap is PARENT : 3 LEFT CHILD : 5 RIGHT CHILD : 6 PARENT : 5 LEF

When deleting min heap function there is no change in the program.but deleting min value function value not displayed

0 0
Add a comment
Know the answer?
Add Answer to:
add/ remove any methods to the program. please post new code and output Min Heap: public...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Can Anyone help me to convert Below code to C++! Thanks For example, in C++, the...

    Can Anyone help me to convert Below code to C++! Thanks For example, in C++, the function headers would be the following: class MaxHeap { vector<int> data; public: MaxHeap() { // ... } int size() { // ... } int maxLookup() { // ... } void extractMax() { // ... } void insert(int data) { // ... } void remove(int index) { // ... } }; ======================== import java.util.Arrays; import java.util.Scanner; public class MaxHeap { Integer[] a; int size; //...

  • // CMPS 390 // MinHeap.java // Complete 4 methods: getMin, add, removeMin, reheap public class MinHeap...

    // CMPS 390 // MinHeap.java // Complete 4 methods: getMin, add, removeMin, reheap public class MinHeap { private Comparable a heap; // array of heap entries private static final int DEFAULT MAX SIZE = 100; private int lastIndex; // index of last entry public MinHeap() { heap = new Comparable (DEFAULT_MAX_SIZE]; lastIndex = 0; } // end default constructor public MinHeap (int maxSize) { heap = new Comparable (maxSize); lastIndex = 0; } // end constructor public MinHeap (Comparable[] entries)...

  • java The following code is an implementation of a HeapPriorityQueue. You are to implement the methods...

    java The following code is an implementation of a HeapPriorityQueue. You are to implement the methods commented with: // TODO: TIP: Do not just go from memory of your assignment implementation, be sure to consider carefully the constructor and method implementation provided to you. NOTE: You do not have to provide an implementation for any methods intentionally omitted public class Heap PriorityQueue implements PriorityQueue private final static int DEFAULT SIZE 10000 private Comparable [ ] storage private int currentSize: public...

  • Please finish all the questions,Thanks Following is Appendix assume the definition of Java class Heap given in the App...

    Please finish all the questions,Thanks Following is Appendix assume the definition of Java class Heap given in the Appendix For this question, a. (2 marks Consider the following heap 30 12 20 19 6 10 18 Given the array representation of a heap discussed in class, what is the array that corre sponds to this heap? b. (5 marks) Successively insert into the heap of part (a.) 22, 35 and 11, in that order. Use the standard heap insertion algorithm....

  • 2. Write MinheapPriorityQueue constructor, which takes an array of data, and construct the max heap priority...

    2. Write MinheapPriorityQueue constructor, which takes an array of data, and construct the max heap priority queue using bottom-up algorithm. The expected run time should be O(n), where n is the total number of data. BubbleDown method is provided. You may test it in this minHeap public class MinHeapPriorityQueue<E extends Comparable<? super E>>{ private E data[]; private int size; public MinHeapPriorityQueue(){ this(100); } public MinHeapPriorityQueue(int cap){ size = 0; data = (E[]) new Comparable[cap]; } public MinHeapPriorityQueue(int[] a){ } public...

  • PROGRAM DESCRIPTION Using the given class definitions for either C++, create a minimum heap that stores...

    PROGRAM DESCRIPTION Using the given class definitions for either C++, create a minimum heap that stores integers and and implements a minimum priority queue. (Your program can be "hard coded" for integers - it does not need to use templates, generics, or polymorphism.) Your data structure must always store its internal data as a heap. Your toString function should return a string with the heap values as a comma separated list, also including the size of the heap as well....

  • Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time...

    Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time complexity is omitted. Any methods/functions below could be changed into something different. I was thinking of changing the method of getting size of list and maybe change from numbers to letters for nodes. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null;...

  • Implement the class MaxHeapPriorityQueue as a heap with the following operations: • MaxHeapPriorityQueue() creates a new...

    Implement the class MaxHeapPriorityQueue as a heap with the following operations: • MaxHeapPriorityQueue() creates a new heap that is empty. It needs no parameters and returns nothing. Note that as discussed in the video lecture, the index range of the array implementation of a heap is 1:n, NOT 0:n-1 • parent(index) returns the value of the parent of heap[index]. index is between 1 and the size of the heap. If index<=1 or index>size of the heap, it returns None •...

  • Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation...

    Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation in Java #########LinkedBinary Tree class######### public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> { //---------------- nested Node class ---------------- /** Nested static class for a binary tree node. */ protected static class Node<E> implements Position<E> { private E element; // an element stored at this node private Node<E> parent; // a reference to the parent node (if any) private Node<E> left; // a reference to the left...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT