Write a program in Java to implement a d-heap data structure that supports the f
ID: 3861923 • Letter: W
Question
Write a program in Java to implement a d-heap data structure that supports the following operations:
deleteMin (and percolate down)
insert
buildHeap
The value of 'd' is input by the user. A sample inputis given below.
Enter heap elements: 31 16 24 21 13
Enter d: 2
Output: Heap (d=2): 13 16 24 31 21
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 1
Enter element to insert: 6
Output: Heap (d=2): 6 16 13 31 21 24
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 1
Enter element to insert: 20
Output: Heap (d=2): 6 16 13 31 21 24 20
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 2
Output: Heap (d=2): 13 16 20 31 21 24
Enter choice: 3
Enter d: 3
Output: Heap (d=3): 13 16 20 31 21 24
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 3
Enter d: 4
Output: Heap with d=4: 13 16 20 31 21 24
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 4
Program Terminated
Your program will be tested with a larger heap with more elements and different d values.
Explanation / Answer
JavaDArtHeap.java:
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
class DaryHeap {
private int d;
private int heapSize;
private int[] heap;
public DaryHeap(int capacity, int numChild) {
heapSize = 0;
d = numChild;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == heap.length;
}
public void clear() {
heapSize = 0;
}
private int parent(int i) {
return (i - 1) / d;
}
private int kthChild(int i, int k) {
return d * i + k;
}
public void insert(int x) {
if (isFull())
throw new NoSuchElementException("Overflow Exception");
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
public int findMin() {
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
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;
}
private void heapifyUp(int childInd) {
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)]) {
heap[childInd] = heap[parent(childInd)];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
private void heapifyDown(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;
}
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;
}
public void printHeap() {
System.out.print(" Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
}
public class JavaDArtHeap {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter size and D of D-ary Heap");
int d = scan.nextInt();
int size = scan.nextInt();
DaryHeap dh = new DaryHeap(d,size);
char ch;
do {
System.out.println(" Heap Operations ");
System.out.println("1. Insert ");
System.out.println("2. Delete");
System.out.println("3. Check full");
System.out.println("4. Check empty");
System.out.println("5. New D value");
boolean chk;
int choice = scan.nextInt();
switch (choice) {
case 1:
try {
System.out.println("Enter integer element to insert");
dh.insert(scan.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 2:
try {
dh.delete(0);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 3:
System.out.println("Full status = " + dh.isFull());
break;
case 4:
System.out.println("Empty status = " + dh.isEmpty());
break;
case 5:
{
System.out.println("Enter value of D");
int newd = scan.nextInt();
DaryHeap dh1 = new DaryHeap(newd, size);
char ch1;
do {
System.out.println(" D-ary Heap Operations with New D value ");
System.out.println("6. Insert ");
System.out.println("7. Delete");
boolean chk1;
int choice1 = scan.nextInt();
switch (choice1) {
case 6:
try {
System.out.println("Enter integer element to insert");
dh.insert(scan.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 7:
try {
dh.delete(0);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
System.out.println("Wrong Entry ");
break;
}
dh.printHeap();
System.out.println(" Enter 'n' to quit ");
ch1 = scan.next().charAt(0);
} while (ch1 == 'Y' || ch1 == 'y');
}
break;
default:
System.out.println("Wrong Entry ");
break;
}
dh.printHeap();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.