Page 267 - DCAP407_DATA_STRUCTURE

Data Structure

2. Fill in the blanks:
(a) …………………………… uses the data structure max-heap which is a complete binary tree
where the element at any node is greater than its children.

(b) …………………………… construction initializes the complete binary tree with n nodes by
placing keys in the given order and then “heapifies” the tree.
(c) The heapsort algorithm uses ………………………… method to convert the initial array into a
heap.
3. Select a suitable choice for every question:
(a) A…………………………… is a set of items with an orderable characteristic called an item’s
priority.
(i) Priority queue

(ii) Heap
(iii) Data structure
(iv) BST
(b) Heapsort is a comparison-based sorting algorithm which has a worst-case
…………………………… runtime.

(i) O(log n
(ii) O(log 2n)
(iii) O(n log n)
(iv) O(n log 2n)
(c) Priority queue can be attained by creating a …………………………
(i) Queue
(ii) Tree

(iii) BST
(iv) Heap
(d) The time efficiency of insertion in heap is ……………………………
(i) O(n log n)
(ii) O(log 2n)
(iii) O(log n)

(iv) O(n log 2n)
14.9 Review Questions
1. “The bottom-up heap construction algorithm checks whether the parental dominance holds over
the key at a node starting with the last parental node and ending with the root.” Discuss.
2. “A heap can be implemented as an array by recording its elements in top-down left-to-right
manner”. Describe in detail.
3. “Binary search property is different from heap property”. Justify.

4. “The heap data structure can be used for an efficient implementation of a priority queue”.
Explain.
5. Represent the max heap and min heap for the data 3, 8, 20, 28, 42, 54.

260 LOVELY PROFESSIONAL UNIVERSITY