Cloud Computing era comes with the advancement of technologies in the fields of processing, storage, bandwidth network access, security of the internet, etc. Several advantages of Cloud Computing include scalability, high computing power, ondemand resource access, high availability, etc. One of the biggest challenges faced by Cloud provider is to schedule incoming jobs to virtual machines(VMs) such that certain constraints satisfied. The development of automatic applications, smart devices, and applications, sensor-based applications need large data storage and computing resources and need output within a particular time limit. Many works have been proposed and commented on various data structures and allocation policies for a realtime job on the cloud. Most of these technologies use a queuebased mapping of tasks to VMs. This work presents a novel, min-heap based VM allocation (MHVA) designed for real-time jobs. The proposed MHVA is compared with a queue based random allocation taking performance metrics makespan and energy consumption. Simulations are performed for different scenarios varying the number of tasks and VMs. The simulation results show that MHVA is significantly better than the random algorithm.