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:
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Java Program to Implement Trie
Java Program to Generate Random Hexadecimal Byte
Extract links from an HTML page
Java Program to Perform Finite State Automaton based Search
Spring Security Authentication Provider
Object Type Casting in Java
Entity To DTO Conversion for a Spring REST API
Connect through a Proxy
Spring Boot - Eureka Server
Java Program to Implement DelayQueue API
Circular Dependencies in Spring
Spring Cloud Bus
Setting Up Swagger 2 with a Spring REST API
Java Program to Generate Random Partition out of a Given Set of Numbers or Characters
How to Iterate Over a Stream With Indices
Generating Random Dates in Java
Uploading MultipartFile with Spring RestTemplate
Introduction to Java 8 Streams
Semaphore trong Java
Custom Thread Pools In Java 8 Parallel Streams
Collect a Java Stream to an Immutable Collection
Java Program to Check if a Matrix is Invertible
Inheritance and Composition (Is-a vs Has-a relationship) in Java
Java Program to Implement Randomized Binary Search Tree
Spring Boot - Tomcat Port Number
Java Program to Implement Heap
Biến trong java
A Guide to Java SynchronousQueue
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Binary Numbers in Java
Serialize Only Fields that meet a Custom Criteria with Jackson