https://www.hackerrank.com/challenges/qheap1

QHEAP1.java

import java.util.HashMap;
import java.util.Scanner;

public class QHEAP1 {
    private static int count = 1;
    private static MinimumHeap<Integer> root = null;
    HashMap<Integer,Integer> h = new HashMap<>();
    public static void main(String args[]) {
        long startTime = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        QHEAP1 q = new QHEAP1();
        int t = sc.nextInt(),k,l;
        while(t-- > 0){
            k = sc.nextInt();
            if(k==1){
                l = sc.nextInt();
                q.addElementToHeap(l);
            }
            else if(k==2){
                l = sc.nextInt();
                q.deleteArbitaryElement(l);
            }
            else if(k==3){
                System.out.println(root.data);
            }
        }
        System.out.println("Printing Heap:");
//        q.printMinHeap(root);
        long endTime = System.currentTimeMillis();
        System.out.println((double) (endTime - startTime) / 1000);
        sc.close();
    }
    private void addElementToHeap(int data){
        if(root==null){
            root = new MinimumHeap<>(data, null, null, null);
            h.put(data,count);
            count++;
            return;
        }
        if(count<1){
            System.out.println("underflow");
            return;
        }
        MinimumHeap<Integer> head = root;
        char[] path = getBinary(count).toCharArray();
        for(int i=path.length-2;i>=0;i--){
            if(path[i]=='0') {
                if(head.left == null) {
                    if(data < head.data){
                        int temp = data;
                        data = head.data;
                        head.data = temp;
                        h.put(head.data, h.get(data));
                    }
                    head.left = new MinimumHeap<>(data, null, null, head);
                    h.put(data, count);
                    count++;
                    return;
                }
                head = head.left;
            }
            else if(path[i]=='1') {
                if(head.right == null) {
                    if(data < head.data){
                        int temp = data;
                        data = head.data;
                        head.data = temp;
                        h.put(head.data, h.get(data));
                    }
                    head.right = new MinimumHeap<>(data, null, null, head);
                    h.put(data, count);
                    count++;
                    return;
                }
                head = head.right;
            }
        }
    }

    private String getBinary(int data){
        StringBuilder res = new StringBuilder("");
        while(data>0){
            res.append(data%2);
            data = data/2;
        }
        return res.toString();
    }

    private void deleteElementFromHeap(int data){
        while(root.data!=data){
            extractMin();
        }
        extractMin();
    }
    private void deleteArbitaryElement(int data){
        if(root==null) return;
        int aux=h.get(data);
        count--;
        if(count==1){
            root=null;
            return;
        }
        /*Tail takes us to the element to be deleted*/
        MinimumHeap<Integer> tail = root;
        // go to that element path
        char[] path = getBinary(aux).toCharArray();
        int i;
        // traverse the path and move along
        for(i=path.length-2;i>=0;i--) {
            if(path[i] == '0')
                tail = tail.left;
            else if(path[i] == '1')
                tail = tail.right;
        }
        // if the element to be deleted doesn't have any children i.e. it's a leaf
        // node, put it's parent left or right as null and return
        if(tail.left==null && tail.right==null){
            if(path[i+1]=='0')
                tail.parent.left=null;
            else if(path[i+1]=='1')
                tail.parent.right=null;
            return;
        }
        /*End takes us to the end of the tree*/
        MinimumHeap<Integer> end = root;
        path = getBinary(count).toCharArray();
        for(i=path.length-2;i>=0;i--) {
            if(path[i] == '0')
                end = end.left;
            else if(path[i] == '1')
                end = end.right;
        }
        // While removing last element, we check if it is attached to the left subtree
        // or right subtree and make the correspondent as null
        if(end.parent.left == end)
            end.parent.left=null;
        else if(end.parent.right == end)
            end.parent.right=null;
        tail.data = end.data;
        heapify(tail);
    }

    private int extractMin(){
        if(root==null) return -1;
        // extract root element
        int min = root.data;
        // before heapifying reduce count to get total number of elements
        count--;
        // take tail at root
        if(count==1){
            root=null;
            return min;
        }
        MinimumHeap<Integer> tail = root;
        // get path to tail in order to replace that with root
        char[] path = getBinary(count).toCharArray();
        int i;
        // traverse the path and move along
        for(i=path.length-2;i>=0;i--) {
            if(path[i] == '0')
                tail = tail.left;
            else if(path[i] == '1')
                tail = tail.right;
        }
        // IMP: this is important, if we didn't link this, tail.parent.left will be
        // root(tail) and this ends up in infinite recursion, so make tail.parent.left
        // or right as null
        if(path[i+1] == '0')
            tail.parent.left = null;
        else if(path[i+1] == '1')
            tail.parent.right = null;
        // put tail.parent as null as tail will become new root
        tail.parent = null;
        // link root.left to tail.left and right, then point root to tail
        tail.left = root.left;
        tail.right = root.right;
        root = tail;
        // if there are more than 1 element that means root.left exists and link it's
        // parent to root similarly for right node
        if(count > 2)
            root.left.parent = root;
        if(count > 3)
            root.right.parent = root;
        // now heapify at root
        heapify(root);
        return min;
    }

    private void heapify(MinimumHeap<Integer> head){
        // This condition never reaches, but just keeping it
        if(head==null)
            return;
        MinimumHeap<Integer> temp = head;
        if(head.left != null && head.left.data < temp.data){
             temp = head.left;
        }
        if(head.right != null && head.right.data < temp.data){
            temp = head.right;
        }
        if(temp != head){
            swap(head, temp);
            heapify(temp);
        }
    }

    private void swap(MinimumHeap<Integer> node1, MinimumHeap<Integer> node2){
        //just swap their data not their entire sub-tree
        int temp = node1.data;
        node1.data = node2.data;
        node2.data = temp;
        h.put(node2.data, h.get(node1.data));
        h.put(node1.data, h.get(node2.data));
/*        if(node1.left == node2) {
            MinimumHeap temp = node1.right;
            MinimumHeap temp2 = node1.parent;
            node1.left = node2.left;
            node1.right = node2.right;
            node1.parent = node2;
            node2.left = node1;
            node2.right = temp;
            node2.parent = temp2;
        }
        else if(node1.right == node2){
            MinimumHeap temp = node1.left;
            MinimumHeap temp2 = node1.parent;
            node1.left = node2.left;
            node1.right = node2.right;
            node1.parent = node2;
            node2.right = node1;
            node2.left = temp;
            node2.parent = temp2;
        }*/
    }

    private void printMinHeap(MinimumHeap root){
        if(root==null)
            return;
        /* TODO: iterative approach */
        System.out.println(root.data);
        printMinHeap(root.left);
        printMinHeap(root.right);
    }
}
class MinimumHeap<T>{
    protected T data;
    protected MinimumHeap<T> left;
    protected MinimumHeap<T> right;
    protected MinimumHeap<T> parent;

    public MinimumHeap(T data, MinimumHeap<T> left, MinimumHeap<T> right, MinimumHeap<T>
            parent){
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

}