Page 205 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes variables are allocated in the space of initialized static variables; the local variables of a procedure
are allocated in the procedure’s activation record, which is typically found in the processor stack;
and dynamically allocated variables are allocated in the heap. In this unit, the term heap is taken
to mean the storage pool for dynamically allocated variables.
I consider heaps and heap-ordered trees in the context of priority queue implementations. While
it may be possible to use a heap to manage a dynamic storage pool, typical implementations do
not. In this context, the technical meaning of the term heap is closer to its dictionary defi nition–”a
pile of many things.”
A binary tree has the heap property iff

1. It is empty or
2. The key in the root is larger than that in either child and both subtrees have the heap
property.
A heap can be used as a priority queue: the highest priority item is at the root and is trivially
extracted. But if the root is deleted, you are left with two sub-trees and you must effi ciently
re-create a single tree with the heap property.
The value of the heap structure is that you can both extract the highest priority item and insert a
new one in O(logn) time.

10.2 Binary Heaps

A binary heap is a heap-ordered binary tree which has a very special shape called a complete
tree. As a result of its special shape, a binary heap can be implemented using an array as the

underlying foundational data structure. Array subscript calculations are used to find the parent
and the children of a given node in the tree. And since an array is used, the storage overhead

associated with the subtree fields contained in the nodes of the trees is eliminated.
10.2.1 Complete Trees

Complete trees and perfect trees are closely related, yet quite distinct. As pointed out in the
preceding unit, a perfect binary tree of height h has exactly n = 2 – 1 internal nodes. Since, the
h+1
only permissible values of n are
0, 1, 3, 7, 15, 31, ..., 2 – 1,... ,
h+1
there is no perfect binary tree which contains, say 2, 4, 5, or 6 nodes.
However, you want a data structure that can hold an arbitrary number of objects so you cannot

use a perfect binary tree. Instead, you use a complete binary tree, which is defined as follows:

Definition (Complete Binary Tree)
A complete binary tree of height h ≥ 0, is a binary tree {R, T , T } with the following properties.
L R
1. If h = 0, T = l and T = l.
L R
2. For h > 0 there are two possibilities:
(a) T is a perfect binary tree of height h-1 and T is a complete binary tree of height h-1;
L R
or
(b) T is a complete binary tree of height h-1 and T is a perfect binary tree of height h-2.
L R
Figure 10.1 shows an example of a complete binary tree of height four. Notice that the left subtree
of node 1 is a complete binary tree of height three; and the right subtree is a perfect binary tree

200 LOVELY PROFESSIONAL UNIVERSITY