This task can be very easily executed using a heap by considering N jobs as N nodes of the tree.Īs you can see in the diagram below, we can use an array to store the nodes of the tree. So at each instant we have to check for the job with maximum priority to complete it and also insert if there is a new job. At each instant we are completing a job with maximum priority and at the same time we are also interested in inserting a new job in the queue with its own priority. The job with maximum priority will get completed first than others. Suppose there are N Jobs in a queue to be done, and each job has its own priority. In the diagram above, you can observe a particular sequence, i.e each node has greater value than any of its children. In binary heap, if the heap is a complete binary tree with N nodes, then it has has smallest possible height which is log 2 N.
However in the more commonly used heap type, there are at most 2 children of a note and it's known as a Binary heap.
The maximum number of children of a node in the heap depends on the type of heap. Let’s say if X is a parent node of Y, then the value of X follows some specific order with respect to value of Y and the same order will be followed across the tree. A heap is a specific tree based data structure in which all the nodes of tree are in a specific order.
