Java Program To Implement Ternary Heap

Chapter: Data Structures Last Updated: 13-07-2016 09:39:50 UTC

Program:

            /* ............... START ............... */
                
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;

class TernaryHeap {
	private int d;
	private int heapSize;
	private int[] heap;

	public TernaryHeap(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("\nHeap = ");
		for (int i = 0; i < heapSize; i++)
			System.out.print(heap[i] + " ");
		System.out.println();
	}
}

public class JavaTernaryHeapExample {

	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");

		TernaryHeap th = new TernaryHeap(scan.nextInt(), scan.nextInt());

		char ch;

		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;
			}
			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');
	}
}

                /* ............... END ............... */
        

Output

Ternary Heap Test


Enter size and no of nodes each child has
3
2

Ternary Heap Operations

1. insert 
2. delete
3. check full
4. check empty
5. clear
1
Enter integer element to insert
1

Heap = 1 

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
12
Wrong Entry 
 

Heap = 1 

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
2

Heap = 1 2 

Do you want to continue (Type y or n) 

n

Notes:

  • Ternary Heap is implemented using concept of D-ary Heap.

Tags

Implement Ternary Heap, Java, Data Structures

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3