This is a Java Program to implement Ternary Heap. Here Ternary Heap is implemented using concept of D-ary Heap.
Here is the source code of the Java program to implement Ternary Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement Ternary-Heap */ import java.util.Scanner; import java.util.Arrays; import java.util.NoSuchElementException; /** Class Ternary Heap **/ class TernaryHeap { private int d; private int heapSize; private int[] heap; /** Constructor **/ public TernaryHeap (int capacity, int numChild) { heapSize = 0; d = numChild; 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 clear( ) { 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 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 heapifyUp **/ 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; } /** Function heapifyDown **/ 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; } /** 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("\nHeap = "); for (int i = 0; i < heapSize; i++) System.out.print(heap[i] +" "); System.out.println(); } } /** Class TernaryHeapTest **/ public class TernaryHeapTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Ternary Heap Test\n\n"); System.out.println("Enter size and no of nodes each child has"); /** Make object of TernaryHeapHeap **/ TernaryHeap th = new TernaryHeap(scan.nextInt(), scan.nextInt() ); char ch; /** Perform Ternary Heap operations **/ do { System.out.println("\nTernary Heap Operations\n"); 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. clear"); boolean chk; int choice = scan.nextInt(); switch (choice) { case 1 : try { System.out.println("Enter integer element to insert"); th.insert( scan.nextInt() ); } catch (Exception e) { System.out.println(e.getMessage() ); } break; case 2 : try { System.out.println("Enter delete position"); th.delete(scan.nextInt() - 1); } catch (Exception e) { System.out.println(e.getMessage() ); } break; case 3 : System.out.println("Full status = "+ th.isFull()); break; case 4 : System.out.println("Empty status = "+ th.isEmpty()); break; case 5 : th.clear(); System.out.println("Heap Cleared\n"); break; default : System.out.println("Wrong Entry \n "); break; } /** Display heap **/ th.printHeap(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
Ternary Heap Test Enter size and no of nodes each child has 3 3 Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 1 Enter integer element to insert 57 Heap = 57 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 1 Enter integer element to insert 17 Heap = 17 57 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 1 Enter integer element to insert 19 Heap = 17 57 19 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 1 Enter integer element to insert 7 Heap = 7 57 19 17 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 1 Enter integer element to insert 24 Overflow Exception Heap = 7 57 19 17 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 2 Enter delete position 2 Heap = 7 17 19 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 2 Enter delete position 1 Heap = 17 19 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 2 Enter delete position 2 Heap = 17 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 4 Empty status = false Heap = 17 Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 5 Heap Cleared Heap = Do you want to continue (Type y or n) y Ternary Heap Operations 1. insert 2. delete 3. check full 4. check empty 5. clear 4 Empty status = true Heap = Do you want to continue (Type y or n) n
Related posts:
Remove HTML tags from a file to extract only the TEXT
Exception Handling in Java
Java Program to Find Basis and Dimension of a Matrix
Simple Single Sign-On with Spring Security OAuth2
Java Program to Implement First Fit Decreasing for 1-D Objects and M Bins
Java Program to Check the Connectivity of Graph Using DFS
A Guide to System.exit()
A Guide to JPA with Spring
Java Program to Implement vector
Java Program to Generate All Possible Combinations of a Given List of Numbers
Hướng dẫn sử dụng String Format trong Java
Guide to CopyOnWriteArrayList
How to Manually Authenticate User with Spring Security
Guide to java.util.concurrent.Locks
Circular Dependencies in Spring
Converting between an Array and a List in Java
Java Program to Implement Network Flow Problem
Java Multi-line String
Using JWT with Spring Security OAuth (legacy stack)
Sử dụng CyclicBarrier trong Java
Java Program to Implement Sorted Singly Linked List
Java – String to Reader
How to Get the Last Element of a Stream in Java?
Spring Data – CrudRepository save() Method
Java – Write a Reader to File
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Beans and Dependency Injection
Java Program to Perform Searching Based on Locality of Reference
Spring Boot - Rest Controller Unit Test
Java Program for Topological Sorting in Graphs
Merging Streams in Java
Disable DNS caching