Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Putting Items into a Binary Heap

There are two requirements which must be satisfied when an item is inserted in a binary heap. First, the resulting tree must have the correct shape. Second, the tree must remain heap-ordered. Figure gif illustrates the way in which this is done.

Since the resulting tree must be a complete tree, there is only one place in the tree where a node can be added. That is, since the bottom level must be filled from left to right, the node node must be added at the next available position in the bottom level of the tree as shown in Figure gif (a).

   figure24264
Figure: Inserting an item into a binary heap.

In this example, the new item to be inserted has the key 2. Note that we cannot simply drop the new item into the next position in the complete tree because the resulting tree is no longer heap ordered. Instead, the hole in the heap is moved toward the root by moving items down in the heap as shown in Figure gif (b) and (c). The process of moving items down terminates either when we reach the root of the tree or when the hole has been moved up to a position in which when the new item is inserted the result is a heap.

Program gif gives the code for inserting an item in a binary heap. The Enqueue method of the BinaryHeap class takes as its argument the item to be inserted in the heap. If the priority queue is full an exception is thrown. Otherwise, the item is inserted as described above.

   program24577
Program: BinaryHeap class Enqueue method.

The implementation of the algorithm is actually remarkably simple. Lines 11-15 move the hole in the heap up by moving items down. When the loop terminates, the new item can be inserted at position i. Therefore, the loop terminates either at the root, i=1, or when the key in the parent of i, which is found at position tex2html_wrap_inline65499, is smaller than the item to be inserted.

Notice too that a good optimizing compiler will recognize that the subscript calculations involve only division by two. Therefore, the divisions can be replaced by bitwise right shifts which usually run much more quickly.

Since the depth of a complete binary tree with n nodes is tex2html_wrap_inline65549, the worst case running time for the Enqueue operation is

displaymath65537

where tex2html_wrap_inline65551 is the time required to compare to objects. If tex2html_wrap_inline65553, the Enqueue operation is simply tex2html_wrap_inline59121 in the worst case.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.