Write a Java program that implements a class for a binary minHeap data structure
ID: 3682488 • Letter: W
Question
Write a Java program that implements a class for a binary minHeap data structure.
Implement your heap using an array. The minHeap must implement the following functions:
void insert(Event); // the minHeap insert algorithm
void add(Event); // adds the event to the next available array slot, no percolation
Event deleteMin(); // removes and returns the event with the smallest timeOfEvent
boolean isEmpty();
void buildHeap(); // the minHeap buildHeap algorithm
“Event” is a base class for three types of events, Arrival, EndOfService and Termination. Each of these has a class variable, double timeOfEvent, and a function void print() that is called when the object is removed from the queue. These print functions print the class name followed by the class variable, as follows:
Arrival Event at time 24.56.
EndOfService Event at time 50.66.
Termination Event at time 71.78.
All doubles must be printed with two digits before the point and two digits after the point. The timeOfEvent field is used as the key for all heap operations.
An input must be read from System.in and all output must be to System.out.
Sample Run:
1. Add Event
2. Insert
3. Print Array
4. Build Heap
5. Delete Min
6. Quit
Option: 1
Event Type: Arrival
Time: 12.10
Done
Option: 1
Event Type: Arrival
Time: 11.45
Done
Option: 1
Event Type: EndOfService
Time: 11.40
Done
Option: 1
Event Type: Termination
Time: 13.45
Done
Option: 2
Can’t insert into the heap use build heap first or just add
Option: 3 Arrival:12.10; Arrival:11.45; EndOfService:11.40; Termination: 13.45
Option: 4 Heap Built
Option: 3 EndOfService :11.40; Arrival:11.45; Arrival:12.10; Termination:13.45
Option: 2 Event Type: Arrival Time: 13.40
Option: 1 Can’t add into the heap use insert
Option: 7 Minimum Deleted EndOfService Event at time 11.40
Option: 3 Arrival:11.45; Arrival 13:40; Arrival:12.10; Termination:13.45
Option: 8 Thank You.
Explanation / Answer
/ * Java Program to Implement Binary Heap
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
class BinaryHeap
{
/* The number of children each node has */
private static final int d = 2;
private int heapSize;
private int[] heap;
/* Constructor */
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
/* Function to check if heap is empty */
public boolean isEmpty( )
{
return heapSize == 0;
}
/* Check if heap is full */
public boolean isFull( )
{
return heapSize == heap.length;
}
/* Clear heap */
public void makeEmpty( )
{
heapSize = 0;
/* Function to get index parent of i */
private int parent(int i)
{
return (i - 1)/d;
}
/* Function to get index of k th child of i */
private int kthChild(int i, int k)
{
return d * i + k;
}
/* Function to insert element */
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("Overflow Exception");
/** Percolate up **/
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
/* Function to find least element */
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
/* Function to delete min element */
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
/* Function to delete element at an index */
public int delete(int ind)
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
/* Function heapUp */
private void heapUp(int childInd)
{
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)])
{
heap[childInd] = heap[ parent(childInd) ];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
/* Function heapDown */
private void heapDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
/* Function to get smallest child */
private int minChild(int ind)
{
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize))
{
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
/* Function to print heap */
public void printHeap()
{
System.out.print(" Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
/* Class BinaryHeapTest */
public class BinaryHeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Binary Heap Test ");
System.out.println("Enter size of Binary heap");
/* Make object of BinaryHeap */
BinaryHeap bh = new BinaryHeap(scan.nextInt() );
char ch;
/* Perform Binary Heap operations */
do
{
System.out.println(" Binary Heap Operations ");
System.out.println("1. insert ");
System.out.println("2. delete min");
System.out.println("3. check full");
System.out.println("4. check empty");
System.out.println("5. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
try
{
System.out.println("Enter integer element to insert");
bh.insert( scan.nextInt() );
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 2 :
try
{
System.out.println("Min Element : "+ bh.deleteMin());
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 3 :
System.out.println("Full status = "+ bh.isFull());
break;
case 4 :
System.out.println("Empty status = "+ bh.isEmpty());
break;
case 5 :
bh.makeEmpty();
System.out.println("Heap Cleared ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display heap */
bh.printHeap();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Binary Heap Test
Enter size of Binary heap
10
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
28
Heap = 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
3
Heap = 3 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
29
Heap = 3 28 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
5
Heap = 3 5 29 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
63
Heap = 3 5 29 28 63
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
18
Heap = 3 5 18 28 63 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
99
Heap = 3 5 18 28 63 29 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 3
Heap = 5 28 18 99 63 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 5
Heap = 18 28 98 99 63
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 18
Heap = 28 63 29 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 28
Heap = 29 63 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 29
Heap = 63 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 63
Heap = 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 99
Heap =
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Underflow Exception
Heap =
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
4
Empty status = true
Heap =
Do you want to continue (Type y or n)
n
/ * Java Program to Implement Binary Heap
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
class BinaryHeap
{
/* The number of children each node has */
private static final int d = 2;
private int heapSize;
private int[] heap;
/* Constructor */
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
/* Function to check if heap is empty */
public boolean isEmpty( )
{
return heapSize == 0;
}
/* Check if heap is full */
public boolean isFull( )
{
return heapSize == heap.length;
}
/* Clear heap */
public void makeEmpty( )
{
heapSize = 0;
/* Function to get index parent of i */
private int parent(int i)
{
return (i - 1)/d;
}
/* Function to get index of k th child of i */
private int kthChild(int i, int k)
{
return d * i + k;
}
/* Function to insert element */
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("Overflow Exception");
/** Percolate up **/
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
/* Function to find least element */
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
/* Function to delete min element */
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
/* Function to delete element at an index */
public int delete(int ind)
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
/* Function heapUp */
private void heapUp(int childInd)
{
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)])
{
heap[childInd] = heap[ parent(childInd) ];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
/* Function heapDown */
private void heapDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
/* Function to get smallest child */
private int minChild(int ind)
{
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize))
{
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
/* Function to print heap */
public void printHeap()
{
System.out.print(" Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
/* Class BinaryHeapTest */
public class BinaryHeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Binary Heap Test ");
System.out.println("Enter size of Binary heap");
/* Make object of BinaryHeap */
BinaryHeap bh = new BinaryHeap(scan.nextInt() );
char ch;
/* Perform Binary Heap operations */
do
{
System.out.println(" Binary Heap Operations ");
System.out.println("1. insert ");
System.out.println("2. delete min");
System.out.println("3. check full");
System.out.println("4. check empty");
System.out.println("5. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
try
{
System.out.println("Enter integer element to insert");
bh.insert( scan.nextInt() );
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 2 :
try
{
System.out.println("Min Element : "+ bh.deleteMin());
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 3 :
System.out.println("Full status = "+ bh.isFull());
break;
case 4 :
System.out.println("Empty status = "+ bh.isEmpty());
break;
case 5 :
bh.makeEmpty();
System.out.println("Heap Cleared ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display heap */
bh.printHeap();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Binary Heap Test
Enter size of Binary heap
10
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
28
Heap = 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
3
Heap = 3 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
29
Heap = 3 28 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
5
Heap = 3 5 29 28
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
63
Heap = 3 5 29 28 63
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
18
Heap = 3 5 18 28 63 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
1
Enter integer element to insert
99
Heap = 3 5 18 28 63 29 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 3
Heap = 5 28 18 99 63 29
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 5
Heap = 18 28 98 99 63
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 18
Heap = 28 63 29 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 28
Heap = 29 63 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 29
Heap = 63 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 63
Heap = 99
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Min Element : 99
Heap =
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
2
Underflow Exception
Heap =
Do you want to continue (Type y or n)
y
Binary Heap Operations
1. insert
2. delete min
3. check full
4. check empty
5. clear
4
Empty status = true
Heap =
Do you want to continue (Type y or n)
n
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.