Write a program in Java to implement a d-heap data structure that supports the f

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

Note: Program will be tested with a larger heap with more elements and different d values.

Explanation / Answer

import javax.swing.JOptionPane; public class DairyHeap { /** * Construct the binary heap. */ public DairyHeap( ) { this( DEFAULT_CAPACITY, DEFAULT_D ); } /** * Construct the binary heap. * @param capacity the capacity of the binary heap. */ public DairyHeap( int capacity, int numKids ) { currentSize = 0; d = numKids; array = new Comparable[ capacity + 1 ]; } /** * Construct the binary heap. * @param an array to be heapified. Note it is assumed this array does * not have data stored in the zeroth element */ public DairyHeap( Comparable [] array, int numKids ) { int i = 0; while (array[i] != null) i++; currentSize = i; this.array = array; this.d = numKids; buildHeap(); } // In binary heaps, parent(i) returns (i-1)/2 // Here, parent(i) returns the index corresponding to the parent of i... private int parent(int i) { return (i-1)/d; } // In binary heaps, leftChild(i) returns 2*i + 1, and rightChild(i) returns 2*i + 2... // Here, kthChild(i, k) returns the index corresponding to the kth child of i... // Note: leftmost child is the first child of i, next comes the second child of i, etc. up till the dth child of i... private int kthChild(int i, int k) { return d*i + k; } /** * Insert into the priority queue, maintaining heap order. * Duplicates are allowed. * @param x the item to insert. * @exception Overflow if container is full. */ public void insert( Comparable x ) throws Overflow { if( isFull( ) ) throw new Overflow( ); // Percolate up int hole = currentSize; currentSize++; array[hole] = x; percolateUp(hole); } /** * Remove the smallest item from the priority queue. * @return the smallest item, or null, if empty. */ public Comparable deleteMin( ) { if( isEmpty( ) ) return null; Comparable minItem = findMin( ); array[ 0 ] = array[ currentSize-1 ]; currentSize--; percolateDown( 0 ); return minItem; } /** * Remove the item from array[hole] from the heap. * And, we adjust the heap accordingly. * @return the smallest item, or null, if empty. */ public Comparable delete( int hole ) { if( isEmpty( ) ) return null; Comparable keyItem = array[hole]; array[ hole ] = array[ currentSize-1 ]; currentSize--; percolateDown( hole ); return keyItem; } /** * Establish heap order property from an arbitrary * arrangement of items. Runs in linear time. */ private void buildHeap( ) { for( int i = currentSize - 1 ; i >= 0; i-- ) percolateDown( i ); } /** * Test if the priority queue is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return currentSize == 0; } /** * Test if the priority queue is logically full. * @return true if full, false otherwise. */ public boolean isFull( ) { return currentSize == array.length; } private static final int DEFAULT_CAPACITY = 100; private static final int DEFAULT_D = 3; private int d; // The number of children each node has. And when d=2, we've got a binary heap... private int currentSize; // Number of elements in heap private Comparable [ ] array; // The heap array /** * Internal method to percolate down in the heap. * @param hole the index at which the percolate begins. */ private void percolateDown( int hole ) { /* 1*/ int child; /* 2*/ Comparable tmp = array[ hole ]; /* 3*/ for( ; kthChild(hole, 1)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.