I am able to implement HPA using metrics-server as heapster is depreciated. I have followed the following steps:

1. Clone the metrics-server github repo: git clone https://github.com/kubernetes-incubator/metrics-server.git

Go into directory cd deploy/1.8+ and run following yaml files:

[root@ip-10-0-1-91 1.8+]# kubectl apply -f aggregated-metrics-reader.yaml 
clusterrole.rbac.authorization.k8s.io/system:aggregated-metrics-reader created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f auth-reader.yaml 
rolebinding.rbac.authorization.k8s.io/metrics-server-auth-reader created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f auth-delegator.yaml 
clusterrolebinding.rbac.authorization.k8s.io/metrics-server:system:auth-delegator created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f metrics-apiservice.yaml 
apiservice.apiregistration.k8s.io/v1beta1.metrics.k8s.io created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f resource-reader.yaml 
clusterrole.rbac.authorization.k8s.io/system:metrics-server created
clusterrolebinding.rbac.authorization.k8s.io/system:metrics-server created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f metrics-server-deployment.yaml 
serviceaccount/metrics-server created
deployment.extensions/metrics-server created
[root@ip-10-0-1-91 1.8+]# kubectl apply -f metrics-server-service.yaml 
service/metrics-server created

Now create a pod you want to test for autoscaling (taken from kubernetes official docs):

[root@ip-10-0-1-91 auto]#  kubectl run --generator=run-pod/v1 php-apache -- 
image=k8s.gcr.io/hpa-example --requests=cpu=200m --expose --port=80
service/php-apache created
deployment.apps/php-apache created

Now create a autoscale deployment:

[root@ip-10-0-1-91 auto]# kubectl autoscale deployment php-apache --cpu-percent=50 --min=1 --max=10
horizontalpodautoscaler.autoscaling/php-apache autoscaled

Now check the HPA, your metrics are coming or not:

[root@ip-10-0-1-91 manifests]# kubectl get hpa
NAME         REFERENCE               TARGETS   MINPODS   MAXPODS   REPLICAS   AGE
php-apache   Deployment/php-apache   0%/50%    1         10        1          2m

Now generate load from another window using:

kubectl run -i --tty load-generator --image=busybox /bin/sh

It will open a sh terminal and you can run a load from that sh terminal using:

while true; do wget -q -O- http://php-apache.default.svc.cluster.local; done

It will take a minute or so to take enough load on your pod and you see a boom:

[root@ip-10-0-1-91 manifests]# kubectl get hpa
NAME         REFERENCE               TARGETS    MINPODS   MAXPODS   REPLICAS   AGE
php-apache   Deployment/php-apache   120%/50%   1         10        4          7m

And pods scaling :

Hope this helps to get your HPA working.

EDIT:

Replace the metrics-server-deployment.yaml file in deploy/1.8+ with the following yaml file:

 apiVersion: v1
 kind: ServiceAccount
 metadata:
   name: metrics-server
   namespace: kube-system
 ---
 apiVersion: extensions/v1beta1
 kind: Deployment
 metadata:
   name: metrics-server
   namespace: kube-system
   labels:
     k8s-app: metrics-server
 spec:
   selector:
     matchLabels:
       k8s-app: metrics-server
   template:
     metadata:
       name: metrics-server
       labels:
         k8s-app: metrics-server
     spec:
       serviceAccountName: metrics-server
       volumes:
       # mount in tmp so we can safely use from-scratch images and/or read-only containers
       - name: tmp-dir
         emptyDir: {}
       containers:
       - command:
         - /metrics-server
         - --metric-resolution=30s
         - --kubelet-insecure-tls
         - --kubelet-preferred-address-types=InternalIP
         name: metrics-server
         image: k8s.gcr.io/metrics-server-amd64:v0.3.1
         imagePullPolicy: Always
         volumeMounts:
         - name: tmp-dir
           mountPath: /tmp

Also, enable the --authentication-token-webhook in kubelet.conf, then you will be able to get the HPA.

EDIT2: You need to set following properties in the deployment file (in your case it is tomcat) for which you are creating HPA, then only your HPA can fetch metrics from your deployment.

resources:
  requests:
    memory: "64Mi"
    cpu: "250m"
  limits:
    memory: "128Mi"
    cpu: "500m"