Let us look at a data structure problem involving job schedulers. Job scheduler maintains a list of pending jobs with priorities.

Now, the job scheduler has to choose the next job to execute at any point. So, whenever the processor is free it picks the job, not the job which arrived earliest, but the one with maximum priority in the list and then schedules it. New jobs keep joining the list, each with its own priority and according to their priority they get promoted ahead of other jobs which may have joined earlier. So, our question is how should the scheduler maintain the list of pending jobs and their priorities? So that it can always pull out very quickly the one with the highest priority to schedule next.

There are two operations associated with the priority queue, one is delete max. In delete queue we just said we take the element at the head of the queue. In delete max we have to look through the queue and identify and remove the job with the highest priority. Note of course, that the priorities of two different jobs may be the same in which case we can pick any one, and the other operation is which we normally called add to the queue we will call insert and insert just adds a new job to the list and each job when it is added comes with its own priority.

Based on linear structures that we already studied, we can think of maintaining these jobs just as a list. Now, if it is an unsorted list when we add something to the queue we can just add it to the list appended in any position. This takes constant time; however, to do a delete max we have to scan through the list and search for the maximum element and as we have seen in an unsorted list, it will take us order n time to find the maximum element in the list because we have to scan all the items.

The other option is to keep the list sorted. This helps to delete max; for instance, if we keep it sorted in descending order the first element of the list is always the largest element. However, the price we pay is for inserting because, to maintain the sorted order, when we insert the element we have to put it in the right position and as we saw in insertion sort, insert will take linear time. So, as a trade-off we either take linear time for delete max or linear time for insert. If we think of n jobs entering and leaving the queue one way or another we end up spending n squared time processing these n jobs.

This is the fundamental limitation of keeping the data in a one-dimensional structure. Let us look at two-dimensional structures; the most basic two-dimensional structure that we can think of is a binary tree. A binary tree consists of nodes, and each node has a value stored in it and it has possibly a left and a right child. We start at the root which is the top of the tree and then each node will have 1 or 2 children. A node which has no children is called a leaf.

Our goal is to maintain a priority queue as a special kind of binary tree which we will call a heap. This tree will be balanced. A balanced tree is one in which roughly speaking at each point the left and right sides are almost the same size. Because of this, it turns out that in a balanced tree, if we have n nodes then the height of the tree will be logarithmic because remember that the height doubles with each level and as a result of which we can fit n nodes in log n levels provided it is balanced and because it is of height log n, we will achieve both insert and delete max in order log n time.