244 BINARY TREES [CHAP. 10
Fig. 10-10number of moves cannot exceed the depthdof the tree. Thus the running timef (n)of either algorithm depends
on the depthdof the treeT.
Now supposeThas the property that, for any nodeNofT, the depths of the subtrees ofNdiffer by at most 1.
Then the treeTis said to be balanced, andd≈log 2 n. Therefore, the running timef (n)of either algorithm in
a balanced tree is very fast; specifically,f (n)= 0 (log 2 n). On the other hand, as items are added into a binary
search treeT, there is no guarantee thatTremains balanced. It could even happen thatd≈n. In this case,f (n)
would be relatively slow; specifically,f (n)= 0 (n). Fortunately, there are techniques for rebalancing a binary
search treeTas elements are added toT. Such techniques, however, lie beyond the scope of this text.
10.7Priority Queues, Heaps
LetSbe a priority queue.That is,Sis a set where elements may be periodically inserted and deleted, but where
the current largest element (element with highest priority) is always deleted. One may maintainSin memory as
follows:(a) Linear array:Here one can easily insert an element by simply adding it to the end of the array. However, it
is expensive to search for and find the largest element, since one must use a linear search with running time
f (n)= 0 (n).
(b)Sorted linear array:Here the largest element is either first or last, and so it is easily deleted. However,
inserting and deleting elements is expensive since, on the average, it involves moving 0(n)elements.This section introduces a discrete structure which can efficiently implement a priority queueS.
Heaps
SupposeHis a complete binary tree withnelements. We assumeHis maintained in memory using its
sequential representation, not a linked representation. (See Section 10.4.)
Definition 10.1:SupposeHis a complete binary tree. ThenHis called aheap,oramaxheap, if each nodeN
has the following property.
The value ofNis greater than or equal to the value at each of the children ofN.