Heap Operations Quiz for Grade 11

1. What is the primary property of a max-heap?

Parent node is greater than or equal to its children

Parent node is less than or equal to its children

All levels must be completely filled

Left child is always greater than right child

In a max-heap, each parent node must be greater than or equal to its children, ensuring that the maximum value is always at the root. This property allows for efficient retrieval of the maximum element and maintains the heap structure during insertion and deletion operations.

Explanation

In a max-heap, each parent node must be greater than or equal to its children, ensuring that the maximum value is always at the root. This property allows for efficient retrieval of the maximum element and maintains the heap structure during insertion and deletion operations.

2. In a binary heap represented as an array, what is the parent index of element at index 5?

2

3

4

6

In a binary heap, the parent index of any element at index \( i \) can be calculated using the formula \( \text{parent index} = \frac{i - 1}{2} \). For index 5, this results in \( \frac{5 - 1}{2} = 2 \), indicating that the parent of the element at index 5 is located at index 2.

Explanation

In a binary heap, the parent index of any element at index \( i \) can be calculated using the formula \( \text{parent index} = \frac{i - 1}{2} \). For index 5, this results in \( \frac{5 - 1}{2} = 2 \), indicating that the parent of the element at index 5 is located at index 2.

3. Which operation restores the heap property by moving an element up the tree?

Heapify-down

Bubble-up

Sift-down

Percolate

Bubble-up is an operation used in heap data structures to restore the heap property by moving an element upwards in the tree. When an element is added or modified, it may violate the heap property, and bubble-up ensures the element is placed correctly by repeatedly swapping it with its parent until the property is satisfied.

Explanation

Bubble-up is an operation used in heap data structures to restore the heap property by moving an element upwards in the tree. When an element is added or modified, it may violate the heap property, and bubble-up ensures the element is placed correctly by repeatedly swapping it with its parent until the property is satisfied.

4. What is the time complexity of inserting an element into a binary heap?

O(1)

O(log n)

O(n)

O(n log n)

Inserting an element into a binary heap requires maintaining the heap property, which may involve moving the newly added element up the tree to its correct position. This process, known as "bubbling up" or "sifting up," can take time proportional to the height of the heap, which is logarithmic relative to the number of elements, thus O(log n).

Explanation

Inserting an element into a binary heap requires maintaining the heap property, which may involve moving the newly added element up the tree to its correct position. This process, known as "bubbling up" or "sifting up," can take time proportional to the height of the heap, which is logarithmic relative to the number of elements, thus O(log n).

5. In a min-heap, the smallest element is always located at ____.

In a min-heap, the structure is designed such that each parent node is less than or equal to its child nodes. This property ensures that the smallest element, which is the minimum value, is always found at the root of the heap. Thus, the root serves as the access point for the smallest element in the min-heap.

Explanation

In a min-heap, the structure is designed such that each parent node is less than or equal to its child nodes. This property ensures that the smallest element, which is the minimum value, is always found at the root of the heap. Thus, the root serves as the access point for the smallest element in the min-heap.

Submit

6. The process of building a heap from an unsorted array is called ____.

Heapify is the process of rearranging the elements of an unsorted array to satisfy the heap property, which can be either a max-heap or a min-heap. This ensures that each parent node is greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) its child nodes, creating a valid heap structure.

Explanation

Heapify is the process of rearranging the elements of an unsorted array to satisfy the heap property, which can be either a max-heap or a min-heap. This ensures that each parent node is greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) its child nodes, creating a valid heap structure.

Submit

7. True or False: A binary heap must be a complete binary tree.

True

False

A binary heap is defined as a complete binary tree, meaning all levels are fully filled except possibly for the last level, which is filled from left to right. This structure ensures efficient operations like insertion and deletion, maintaining the heap property while preserving the complete tree structure.

Explanation

A binary heap is defined as a complete binary tree, meaning all levels are fully filled except possibly for the last level, which is filled from left to right. This structure ensures efficient operations like insertion and deletion, maintaining the heap property while preserving the complete tree structure.

8. What happens when you remove the root from a max-heap?

Replace root with last element, then heapify-down

Shift all elements left

Delete the largest element immediately

Promote the largest child to root

Removing the root from a max-heap involves replacing it with the last element to maintain the complete binary tree structure. After this replacement, the heap property must be restored, which is achieved by "heapifying down" the new root, ensuring that it is smaller than its children and maintaining the max-heap property.

Explanation

Removing the root from a max-heap involves replacing it with the last element to maintain the complete binary tree structure. After this replacement, the heap property must be restored, which is achieved by "heapifying down" the new root, ensuring that it is smaller than its children and maintaining the max-heap property.

9. For an array-based heap, the left child of node at index i is at index ____.

In an array-based heap, the structure is organized such that for any node at index i, the left child can be found at index 2i + 1. This formula arises from the way heaps are represented in arrays, where each parent node has its children positioned sequentially in the array.

Explanation

In an array-based heap, the structure is organized such that for any node at index i, the left child can be found at index 2i + 1. This formula arises from the way heaps are represented in arrays, where each parent node has its children positioned sequentially in the array.

Submit

10. Which of these is a valid application of heaps?

Priority queue implementation

Sorting (heap sort)

Graph algorithms (Dijkstra)

All of the above

Heaps are versatile data structures that efficiently support various applications. They enable priority queue implementations by allowing quick access to the highest (or lowest) priority element. Additionally, heaps are integral to heap sort, a sorting algorithm, and they enhance graph algorithms like Dijkstra's by efficiently managing the priority of nodes during traversal.

Explanation

Heaps are versatile data structures that efficiently support various applications. They enable priority queue implementations by allowing quick access to the highest (or lowest) priority element. Additionally, heaps are integral to heap sort, a sorting algorithm, and they enhance graph algorithms like Dijkstra's by efficiently managing the priority of nodes during traversal.

11. True or False: A heap is always a sorted array.

True

False

A heap is a specialized tree-based data structure that satisfies the heap property, where the parent node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children. This structure does not guarantee that the elements are sorted in a linear order, hence it is not always a sorted array.

Explanation

A heap is a specialized tree-based data structure that satisfies the heap property, where the parent node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children. This structure does not guarantee that the elements are sorted in a linear order, hence it is not always a sorted array.

12. What is the maximum number of elements at level k in a complete binary heap?

2^k

2^(k-1)

K

2k

In a complete binary heap, each level \( k \) can have up to \( 2^k \) nodes. This is because the first level (root) has 1 node, the second level has 2 nodes, the third level has 4 nodes, and so forth, following the pattern of powers of 2. Thus, the maximum number of elements at level \( k \) is \( 2^k \).

Explanation

In a complete binary heap, each level \( k \) can have up to \( 2^k \) nodes. This is because the first level (root) has 1 node, the second level has 2 nodes, the third level has 4 nodes, and so forth, following the pattern of powers of 2. Thus, the maximum number of elements at level \( k \) is \( 2^k \).