Java Program To Implement D Ary Heap

Chapter: Data Structures Last Updated: 13-07-2016 09:46:51 UTC

Program:

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

class DaryHeap {

	private int d;
	private int heapSize;
	private int[] heap;

	public DaryHeap(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 JavaDArtHeapExample {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		System.out.println("D ary Heap Test\n\n");
		System.out.println("Enter size and D of D-ary Heap");
		DaryHeap dh = new DaryHeap(scan.nextInt(), scan.nextInt());

		char ch;

		do {
			System.out.println("\nD-ary 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");
					dh.insert(scan.nextInt());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 2:
				try {
					System.out.println("Enter delete position");
					dh.delete(scan.nextInt() - 1);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 3:
				System.out.println("Full status = " + dh.isFull());
				break;
			case 4:
				System.out.println("Empty status = " + dh.isEmpty());
				break;
			case 5:
				dh.clear();
				System.out.println("Heap Cleared\n");
				break;
			default:
				System.out.println("Wrong Entry \n ");
				break;
			}
			dh.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

D ary Heap Test


Enter size and D of D-ary Heap
2
2

D-ary 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

D-ary Heap Operations

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

Heap = 1 3 

Do you want to continue (Type y or n) 

y

D-ary 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) 

n

Notes:

  • A heap is a specialized tree-based data structure that satisfies the heap property.

Tags

Implement D Ary Heap, Java, Data Structure

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