Test: Binary Heaps - Computer Science Engineering (CSE) MCQ

Following is algorithm for building a Heap of an input array A.

BUILD-HEAP(A)
         heapsize := size(A);
         for i := floor(heapsize/2) downto 1
              do HEAPIFY(A, i);
         end for
END

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

In Heapsort, we first build a heap, then we do following operations till the heap size becomes 1. a) Swap the root with last element b) Call heapify for root c) reduce the heap size by 1. In this question, it is given that heapify has been called few times and we see that last two elements in given array are the 2 maximum elements in array. So situation is clear, it is maxheapify whic has been called 2 times.

Following 3-ary Max Heap can be constructed from sequence given option (D)

After insertion of 7

After insertion of 2

After insertion of 10

After insertion of 4

A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data. In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

For Heap trees, deletion of a node includes following two operations. 1) Replace the root with last element on the last level. 2) Starting from root, heapify the complete tree from top to bottom.. Let us delete the two nodes one by one: 1) Deletion of 25: Replace 25 with 12

13 10 8

Since heap property is violated for root (16 is greater than 12), make 16 as root of the tree.

2) Deletion of 16: Replace 16 with 8

Heapify from root to bottom.

We can reduce the problem to Build Heap for 2n elements. Time taken for build heap is O(n)

The 7th smallest element must be in first 7 levels. Total number of nodes in any Binary Heap in first 7 levels is at most 1 + 2 + 4 + 8 + 16 + 32 + 64 which is a constant. Therefore we can always find 7th smallest element in time. If Min-Heap is allowed to have duplicates, then time complexity becomes Θ(Log n). Also, if Min-Heap doesn't allow directly accessing elements below root and supports only extract-min() operation, then also time complexity becomes Θ(Log n).

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

32, 15, 20, 30, 12, 25, 16
After insertion of 32, 15 and 20

After insertion of 30

Max Heap property is violated, so 30 is swapped with 15

After insertion of 12

After insertion of 25

Max Heap property is violated, so 25 is swapped with 20

After insertion of 16

We can build a heap of 2n elements in O(n) time. Following are the steps. Create an array of size 2n and copy elements of both heaps to this array. Call build heap for the array of size 2n. Build heap operation takes O(n) time.

Initially heap has 10, 8, 5, 3, 2

After insertion of 1

No need to heapify as 5 is greater than 1.

After insertion of 7

Heapify 5 as 7 is greater than 5

No need to heapify any further as 10 is greater than 7

The merge operation takes O(n) time, all other operations given in question take O(Logn) time. The Binomial and Fibonacci Heaps do merge in better time complexity.

Binary heaps can be represented using arrays: storing elements in an array and using their relative positions within the array to represent child-parent relationships. For the binary heap element stored at index i of the array, Parent Node will be at index: floor(i/2) Left Child will be at index: 2i Right child will be at index: 2*i + 1

The array 40, 30, 20, 10, 15, 16, 17, 8, 4 represents following heap

After insertion of 35, we get

After swapping 35 with 15 and swapping 35 again with 30, we get

〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉

Minimum number of swaps required to convert above tree to Max heap is 3. Below are 3 swap operations.
Swap 100 with 15
Swap 100 with 50
Swap 100 with 89

For this question, we have to slightly tweak the delete_min() operation of the heap data structure to implement the delete(i) operation. The idea is to empty the spot in the array at the index i (the position at which element is to be deleted) and replace it with the last leaf in the heap (remember heap is implemented as complete binary tree so you know the location of the last leaf), decrement the heap size and now starting from the current position i (position that held the item we deleted), shift it up in case newly replaced item is greater than the parent of old item  (considering max-heap).  If it’s not greater than the parent, then percolate it down by comparing with the child’s value. The newly added item can percolate up/down a maximum of d times which is the depth of the heap data structure. Thus we can say that complexity of delete(i) would be O(d) but not O(1).

here node with integer 1 has to be at root only. Now for maximum depth of the tree the following arrangement can be taken. Take root as level 1. make node 2 at level 2 as a child node of node 1. make node 3 at level 3 as the child node of node 2. .. .. and so on for nodes 4,5,6,7 .. make node 8 at level 8 as the child node of node 7. make node 9 at level 9 as the child node of node 8. Putting other nodes properly, this arrangement of the the complete binary tree will follow the property of min heap. So total levels are 9. node 9 is at level 9 and depth of node 9 is 8 from the root.

When they are asking for heap, by default it's max heap. Basic Requirement: Array representation of binary tree Starting from basics lets first understand heap trees We have 2 types of heap – Min heap and Max heap In Min heap the parent is always smaller than its children and in Max heap parent is always greater than its children.

Looking at the options we can tell that which tree is Max heap tree. Now consider each option one by one and draw a tree

From options it is clear that only option C satisfies the Max heap tree property.