Heaps Code

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
Heaps Code
```plaintext
Goal: Given the following MinHeap class, implement the remove() method.

Requirements: Your code should be as efficient as possible. You may not assume any other method in the MinHeap class is implemented. You may assume that everything from java.util is imported.

public class MinHeap<T> {

    private T[] backingArray;
    int size;

    /**
     * Removes and returns the smallest element in the MinHeap.
     *
     * The order property of the heap must be maintained after removing.
     *
     * @return the smallest data in the heap
     * @throws java.util.NoSuchElementException if the heap is empty
     */
    public T remove() {
        // YOUR CODE HERE, USE THE NEXT PAGE IF NEEDED
    }
}

Because this method is on your homework, this code cannot be provided :(
Please refer to feedback on your homework.
```

### Explanation

In the provided Java code for a `MinHeap` implementation, you are required to define the `remove()` method. This method should efficiently remove and return the smallest element from the heap, while maintaining the heap property. No other methods of the `MinHeap` class are assumed to be implemented, but you can utilize any necessary utilities from `java.util`. The `remove()` method should throw a `java.util.NoSuchElementException` if the heap is empty. The focus is on ensuring optimal performance in your implementation, per the class's specifications.
Transcribed Image Text:```plaintext Goal: Given the following MinHeap class, implement the remove() method. Requirements: Your code should be as efficient as possible. You may not assume any other method in the MinHeap class is implemented. You may assume that everything from java.util is imported. public class MinHeap<T> { private T[] backingArray; int size; /** * Removes and returns the smallest element in the MinHeap. * * The order property of the heap must be maintained after removing. * * @return the smallest data in the heap * @throws java.util.NoSuchElementException if the heap is empty */ public T remove() { // YOUR CODE HERE, USE THE NEXT PAGE IF NEEDED } } Because this method is on your homework, this code cannot be provided :( Please refer to feedback on your homework. ``` ### Explanation In the provided Java code for a `MinHeap` implementation, you are required to define the `remove()` method. This method should efficiently remove and return the smallest element from the heap, while maintaining the heap property. No other methods of the `MinHeap` class are assumed to be implemented, but you can utilize any necessary utilities from `java.util`. The `remove()` method should throw a `java.util.NoSuchElementException` if the heap is empty. The focus is on ensuring optimal performance in your implementation, per the class's specifications.
Expert Solution
Step 1

Solution-

According to the question we create an program in which we perform various method like Removing minimum value from  heap and printing it ,for Swapping two nodes of the heap,returning the location of the parent for the node that is presently located at position,    providing/returning  the location of the right and left child for the node that is presently at position,for Swapping two nodes of the heap.. by these methods you may easily understand the concept of heap.

Code-:

// Java Program to Implement Heaps by illustrate min heap

// Main class (MinHeap)
class heap {
 
//Members of this class's variables
    private int[] Heap;
    private int size;
    private int maxsize;
 
    //setting up the front as static using unity
    private static final int FRONT = 1;
 
    // Constructor of this class
    public heap(int maxsize)
    {
 
//This keyword refers to the current object.
this.maxsize = maxsize;
        this.size = 0;
 
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MIN_VALUE;
    }
 
    // Method-: 1
    // returning the location of the parent for the node that is presently located at position
    private int parent(int pos) { return pos / 2; }
 
    // Method 2
    // providing/returning the node at position with the position of the  left child for that node.
    private int leftChild(int pos) { return (2 * pos); }
 
    // Method-; 3
    // providing/returning  the location of the right child for the node that is presently at position
    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }
 
    // Method-:4
    // if the supplied / node is a leaf node, returning true
    private boolean isLeaf(int pos)
    {
 
        if (pos > (size / 2)) {
            return true;
        }
 
        return false;
    }
 
    // Method 5
    //  for Swapping two nodes of the heap
    private void swap(int fpos, int spos)
    {
 
        int tmp;
        tmp = Heap[fpos];
 
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }
 
    // Method 6
    // To heapify the node at that pos
   private void minHeapify(int pos)
   {      
     if(!isLeaf(pos)){
       int swapPos= pos;
       // To determine if the right child is present, switch with the less of the two youngsters. If not, the default value will be "0," and the parent node will be switched in its place.
if(rightChild(pos)<=size)
          swapPos = Heap[leftChild(pos)]<Heap[rightChild(pos)]?leftChild(pos):rightChild(pos);
       else
         swapPos= Heap[leftChild(pos)];
        
       if(Heap[pos]>Heap[leftChild(pos)] || Heap[pos]> Heap[rightChild(pos)]){
         swap(pos,swapPos);
         minHeapify(swapPos);
       }
        
     }       
   }
 
    // Method 7
    // To insert a node into the heap
    public void insert(int element)
    {
 
        if (size >= maxsize) {
            return;
        }
 
        Heap[++size] = element;
        int current = size;
 
        while (Heap[current] < Heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
 
    // Method 8
    // To print the contents of the heap
    public void print()
    {


        for (int i = 1; i <= size / 2; i++) {
 
            // Printing the parent and both childrens
            System.out.print(
                " PARENT : " + Heap[i]
                + " LEFT CHILD : " + Heap[2 * i]
                + " RIGHT CHILD :" + Heap[2 * i + 1]);
 
            // By here new line is required
            System.out.println();
        }
    }
 
    // Method 9
    // To remove and return the minimum
    // element from the heap
    public int remove()
    {
 
        int popped = Heap[FRONT];
        Heap[FRONT] = Heap[size--];
        minHeapify(FRONT);
 
        return popped;
    }
 
    // Method 10
    // Main driver method
    public static void main(String[] arg)
    {
 
        // Display message
        System.out.println("The Min Heap is ");
 
        // Creating object opf class in main() methodn
        heap minHeap = new heap(15);
 
        // Inserting element to minHeap
        // using insert() method
 
        // Custom input entries
        minHeap.insert(15);
        minHeap.insert(23);
        minHeap.insert(17);
        minHeap.insert(10);
        minHeap.insert(24);
        minHeap.insert(19);
        minHeap.insert(60);
        minHeap.insert(22);
        minHeap.insert(9);
 
        // Print all elements of the heap
        minHeap.print();
 
        // Removing minimum value from above heap
        // and printing it
        System.out.println("The Min val is "
                           + minHeap.remove());
    }
}

 

The output of the above code is-

java -cp /tmp/ccZ7Cp641q heap
The Min Heap is 
PARENT : 9 LEFT CHILD : 10 RIGHT CHILD :17
PARENT : 10 LEFT CHILD : 15 RIGHT CHILD :24
 PARENT : 17 LEFT CHILD : 19 RIGHT CHILD :60
 PARENT : 15 LEFT CHILD : 23 RIGHT CHILD :22
The Min val is 9

steps

Step by step

Solved in 2 steps with 8 images

Blurred answer
Knowledge Booster
Perception
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education