Accurate estimation of energy expenditure (EE) is a key enabler for many applications of healthcare and wellness. Heart rate (HR) based EE estimation methods typically require extensive training time to establish a relationship between HR and EE. In this work, we propose a method where just the few most representative EE-HR data pairs are used to train the estimation model. Furthermore, we present a systematical methodology based on the ranking of the correlation coefficients between EE and HR to find the least amount of EE-HR data pairs required for training while satisfying the constraint of estimation accuracy. During the experimental evaluation, while the study participants walk and run on a treadmill, our method is compared to three different training paradigms: training the EE-HR model 1) using all available data collected during the experiment, 2) using the EE-HR data only during speed changes (or during monotonic HR changes) and 3) using the EE-HR data pairs collected during constant speed. The results show that our method could maintain a comparable EE estimation performance as shown by only 2~4% changes on the coefficient of variation of root-mean-squared error (CV(RMSE)) for the testing dataset while saving nearly 91-97% training time for each individual.