Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class MinHeap {
- int[] heapElem;
- int size;
- int maxSize;
- private static final int FRONT = 1;
- public MinHeap(int maxsize) {
- this.maxSize = maxsize;
- this.size = 0;
- heapElem = new int[this.maxSize + 1];
- heapElem[0] = Integer.MIN_VALUE;
- }
- int getParent(int pos) {
- return pos / 2;
- }
- int getLeft(int pos) {
- return 2 * pos;
- }
- int getRight(int pos) {
- return 2 * pos + 1;
- }
- boolean isLeaf(int pos) {
- if (pos >= size / 2 && pos <= size) {
- return true;
- }
- return false;
- }
- void swapNode(int p1, int p2) {
- int temp = heapElem[p1];
- heapElem[p1] = heapElem[p2];
- heapElem[p2] = temp;
- }
- void minHeapify(int pos) {
- if (!isLeaf(pos)) {
- if (heapElem[pos] > heapElem[getLeft(pos)] || heapElem[pos] > heapElem[getRight(pos)]) {
- if (heapElem[getLeft(pos)] < heapElem[getRight(pos)]) {
- swapNode(pos, getLeft(pos));
- minHeapify(getLeft(pos));
- } else {
- swapNode(pos, getRight(pos));
- minHeapify(getRight(pos));
- }
- }
- }
- }
- public void insert(int element) {
- if (size >= maxSize) {
- return;
- }
- heapElem[++size] = element;
- int current = size;
- while (heapElem[current] < getParent(current)) {
- swapNode(current, getParent(current));
- current = getParent(current);
- }
- }
- public int remove() {
- int removed = heapElem[FRONT];
- heapElem[FRONT] = heapElem[size--];
- minHeapify(FRONT);
- return removed;
- }
- public void minHeap() {
- for (int pos = (size / 2); pos >= 1; pos--) {
- minHeapify(pos);
- }
- }
- public void print() {
- for (int i = 1; i <= size / 2; i++) {
- System.out.print(" PARENT : " + heapElem[i] + " LEFT CHILD : " + heapElem[2 * i] + " RIGHT CHILD :"
- + heapElem[2 * i + 1]);
- System.out.println();
- }
- }
- // Driver code
- public static void main(String[] arg) {
- System.out.println("The Min Heap is ");
- MinHeap minHeap = new MinHeap(15);
- minHeap.insert(5);
- minHeap.insert(3);
- minHeap.insert(17);
- minHeap.insert(10);
- minHeap.insert(84);
- minHeap.insert(19);
- minHeap.insert(6);
- minHeap.insert(22);
- minHeap.insert(9);
- minHeap.minHeap();
- minHeap.print();
- System.out.println("The Min val is " + minHeap.remove());
- }
- }
Add Comment
Please, Sign In to add comment