Object-Oriented Data-Structures - A Concise and Practical Introduction to Programming Algorithms in Java - page 174

lining up according to grades is informally what is called priority queues ,a
generalization of queues 2 . These priority queues are yet another fundamental
abstract data type lying at the heart of operating systems for performing “nice”
job scheduling tasks. In a priority queue, it is always the object with highest
priority that goes out of the queue first. In case several objects have the same
priorities, the time arrival is taken into account and we operate along the
guidelines of the queue then: “First in first out” for all objects with the same
priority. For the case of a small fixed number of priorities, we may implement
priority queues by declaring an array of queues. But this naive approach is
rather inecient and does not scale up with arbitrary large number of priority
numbers. There are several ways to implement generic priority queues but these
implementations basically all rely on the fundamental notion of heaps .
A heap is a special tree data-structure storing keys at its nodes. Heaps satisfy
the so-called heap property . The heap property is described as follows: For any
pair ( P, Q ) where Q is a child node of parent P , a heap must satisfy:

key( P ) ≥ key( Q ) .

Figure 8.2 depicts a heap. Observe that the maximal element of a heap is always
located at the root . This explains why heaps are related to priority queues since
it is straightforward to get the maximal priority by looking at the root. Heaps
are also complete binary trees , meaning that nodes are added from left to right
until the current level becomes complete (that is, saturated). We then create a
next level and start adding nodes from the left to right side. Figure 8.2 depicts
a heap. Observe that at a given layer the nodes are not ordered.

37

22 31

17

16 2 3

9

12

6

Figure 8.2 A heap is a binary tree specialized so that the keys of all children
are less than the keys of their parents

Heaps can themselves be compactly embedded into arrays since the binary tree
is perfect. For example, the heap of Figure 8.2 can be stored in an array by
2 In simple queues, elements have the same priority.