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:
Error Handling for REST with Spring
Java Program to Implement Iterative Deepening
Java String Conversions
Java Program to Implement Efficient O(log n) Fibonacci generator
Jackson – Change Name of Field
Registration with Spring Security – Password Encoding
Java Program to Implement Patricia Trie
Spring MVC and the @ModelAttribute Annotation
Remove HTML tags from a file to extract only the TEXT
Java Program to Implement Double Order Traversal of a Binary Tree
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Jackson – Bidirectional Relationships
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Copy a List to Another List in Java
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
Instance Profile Credentials using Spring Cloud
Using a Spring Cloud App Starter
Removing all Nulls from a List in Java
Spring Boot - Bootstrapping
Introduction to Using FreeMarker in Spring MVC
Convert Hex to ASCII in Java
Programmatic Transaction Management in Spring
Creating Docker Images with Spring Boot
Giới thiệu Design Patterns
Default Password Encoder in Spring Security 5
Java Program to Generate Randomized Sequence of Given Range of Numbers
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Convert char to String in Java
Giới thiệu Google Guice – Binding
Java Program to Implement Graph Coloring Algorithm
Spring Boot - Google Cloud Platform
Hướng dẫn Java Design Pattern – Factory Method