Here is an implementation of a Heap in java without using array but I have some problem in inserting data in it for example when i insert 1,3,2,5,8 it inserts 5,8 two times one as subtree of 3 and another one as subtree of 2.

```
public class Heap {
private class Node {
    private Node left, right,parent;
    private int key;
    private Node(int key) {
        this.key = key;
    }
}

private Node root;

public void insert(int key) {
     root = insert(root,key,null);
}

private Node insert(Node x, int key,Node parent) {
    if(x == null){
        x = new Node(key);
        x.parent = parent;
        return x;
    }if(x.left == null){
        x.left = insert(x.left, key,x);
    }else if (x.right == null) {
        x.right = insert(x.right, key,x);
    }else{
        x.left = insert(x.left, key,x);
        x.right = insert(x.right, key,x);
    }
    return x;
}

```

}