Page 266 - DCAP407_DATA_STRUCTURE

Unit 14: Heaps

Let us discuss an example. Figure 14.18 represents both the conceptual heap (the binary tree), and its
array representation. As shown, the root 9 is in array [1]. Its left child 7 is in array [2] and right child is
in array[3]. In general, if a node is in array[m], then its left child is in array [m*2], right child in array
[m*2 + 1] and its parent is in array [m/2].

Figure 14.18: Array Representation of Heap

The shape property of the heap guarantees that there are no empty spaces in the array.
14.6 Summary

• The heap data structure is a complete binary tree where each node of the tree relates to an element
of the array that stores the value in the node.
• The two principal ways to construct a heap are by using the bottom-up heap construction
algorithm and the top-down heap construction algorithm
• A heap is used to implement heapsort. Heapsort is a comparison-based sorting algorithm which
has a worst-case of O(n log n) runtime.
• A priority queue is a queue with items having an orderable characteristic called priority. The
objects having the highest priority are always removed first from the priority queues.
• Priority queue can be attained by creating a heap.
14.7 Keywords

Ascending Heap: It is a complete binary tree in which the value of each node is greater than or equal to
the value of its parent.

Heapify: Heapify is a procedure for manipulating heap data structures.

N-ary Tree: An n-ary tree is either an empty tree, or a non-empty set of nodes which consists of a root
and exactly N sub-trees. The degree of each node of an N-ary tree is either zero or N.
Parental Dominance: The key at each node is greater than or equal to the keys of the children and this is
fulfilled automatically for leaf nodes.
14.8 Self Assessment

1. State whether the following statements are true or false:
(a) Heaps are data structures that are suitable for implementing priority queues.
(b) The top-down heap construction algorithm is more efficient and it constructs a heap by
successive deletions of a new key into a previously constructed heap.

(c) To insert a new key into a heap, a new node with key K is added after the last leaf of the
existing heap and K is shifted up to its suitable place in the new heap.

LOVELY PROFESSIONAL UNIVERSITY 259