In the recent times, healthcare sector is using data mining for a variety of tasks out of which, one of them is predictive modelling. The role of data is of utmost important in any data mining task. In order to perform predictive modelling, data is collected, pre-processed, and then predictive model is developed using appropriate learning algorithms. It is observed that medical datasets are inherently heterogeneous having a mix of categorical, nominal, binary, numeric and non-numeric types. Dealing with such heterogeneity is a challenge for mining of heterogeneous datasets. This work aims to design a predictive model for diagnosis of heart disease taking into consideration, the data heterogeneity. In this work, the CVD dataset from Cleveland database of UCI repositories and Echocardiogram data collected from hospital is utilized. The predictive model is developed using a novel approach which employs K Nearest Neighbour learning algorithm which takes into consideration the type of data and then constructs distance measures accordingly. The results are compared with the two learning algorithms namely Decision Tree and Naive Bayes which can handle data heterogeneity inherently. It is found that the novel approach has given promising results. The accuracy of the model developed using the novel approach is found to be 88% as compared to 81% given by baseline k-NN learning algorithm.