Free Printable Python

Worksheets

Python - Heap

Total questions: 15

Worksheet time: 8mins

Name

Class

Date

What is the time complexity of Build Heap operation. Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting ?

$O\left(n\ \cdot\ Log\ n\right)$

$O\left(\ n^2\ \right)$

$O\left(Log\ n\right)$

$O\left(\ n\ \right)$

Which of the following is a max-heap?

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

1,3,5,6,8,9

9,6,3,1,8,5

9,3,6,8,5,1

9,5,6,8,3,1

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

25,12,16,13,10,8,14

25,12,16,10,13,8,14

25,14,16,13,10,8,12

25,14,12,13,10,8,16

In a binary max heap containing n numbers, the smallest element can be found in time ?

O(n)

O( Log(n) )

O( Log(Log(n)) )

O(1)

On which algorithm is heap sort based on?

Fibonacci series

Binary Tree

Priority Queue

Stack

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is

$i\ -\ 1$

$\lfloor\frac{i}{2}\rfloor$ (Floor Function)

$\lceil\frac{i}{2}\rceil$ (Ceiling Function)

$\frac{\left(i+1\right)}{2}$

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

10.

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can

appear is

11.

The minimum number of interchanges needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with the maximum element at the root is

12.

The number of nodes of height h in any complete n - element binary heap is

$h$

$2^h$

$\lceil\frac{n}{2^h}\rceil$ ( Ceiling function )

$\lceil\frac{n}{2^{h+1}}\rceil$ ( Ceiling Function )

13.

Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?

14,13,8,12,10

14,12,13,10,8

14,13,12,8,10

14,13,12,10,8

14.

What is the best case Time Complexity of Heap Sort?

$O\left(n\ \cdot\ \log n\right)$

$O\left(n^2\right)$

$O\left(n\right)$

$O\left(\log\left(\log n\right)\right)$

15.

The descending heap property is

A[Parent(i)] = A[i]

A[Parent(i)] <= A[i]

A[Parent(i)] >= A[i]

A[Parent(i)] > 2 * A[i]

Reset

Python - Heap

Total questions: 15

Worksheet time: 8mins

Similar Resources on Wayground