Heaps and Binary Search Trees Assessment

What is a max heap?

• A max heap is a complete binary tree where each parent node is greater than or equal to its child nodes.

• A max heap is a binary tree where each child node is greater than its parent nodes.

• A max heap is a data structure that allows for efficient searching of minimum values.

• A max heap is a complete binary tree where all nodes have the same value.

Answer explanation

A max heap is defined as a complete binary tree where each parent node is greater than or equal to its child nodes, ensuring the maximum element is always at the root. This makes the first choice the correct answer.

Define a min heap.

• A min heap is a binary tree where each child node is greater than its parent nodes.

• A min heap is a complete binary tree where each parent node is less than or equal to its child nodes.

• A min heap is a data structure that allows for efficient searching of maximum values.

• A min heap is a complete binary tree where each parent node is equal to its child nodes.

Answer explanation

A min heap is defined as a complete binary tree where each parent node is less than or equal to its child nodes, ensuring the smallest element is always at the root. This makes the second choice the correct definition.

What is the primary property of a max heap?

• The primary property of a max heap is that the value of each node is greater than or equal to the values of its children.

• The primary property of a max heap is that the root node is the smallest value in the heap.

• The primary property of a max heap is that the value of each node is less than or equal to the values of its children.

• In a max heap, all nodes have the same value as their children.

Answer explanation

The primary property of a max heap is that each node's value is greater than or equal to its children's values, ensuring the largest element is always at the root. This distinguishes it from other heap types.

Explain the heap sort algorithm in brief.

• Heap sort requires a sorted array as input to function correctly.

• Heap sort is a linear time sorting algorithm that does not use comparisons.

• Heap sort uses a quick sort algorithm to sort elements.

• Heap sort is an efficient sorting algorithm that sorts an array by first creating a max heap and then repeatedly extracting the maximum element.

Answer explanation

Heap sort is an efficient algorithm that begins by building a max heap from the input array. It then repeatedly extracts the maximum element from the heap, placing it at the end of the array, resulting in a sorted array.

What is the time complexity of heap sort?

• O(n)

• O(n^2)

• O(log n)

• O(n log n)

Answer explanation

Heap sort has a time complexity of O(n log n) due to the process of building the heap (O(n)) and then repeatedly extracting the maximum element (O(log n) for each of the n elements). Thus, the overall complexity is O(n log n).

How do you insert an element into a max heap?

• Add the element to the beginning and sort the entire heap.

• Place the element anywhere in the heap without adjustments.

• Insert the element at the root and remove the smallest element.

• Insert the element at the end and bubble it up to maintain the max heap property.

Answer explanation

To insert an element into a max heap, you add it at the end of the heap and then 'bubble it up' to restore the max heap property, ensuring that each parent node is greater than its children.

What is the role of a priority queue?

• The role of a priority queue is to manage a collection of elements where each element has a priority, enabling efficient access to the element with the highest (or lowest) priority.

• To store elements in a sorted order without priority

• To provide a simple stack implementation for last-in-first-out access

• To manage elements based solely on their insertion order

Answer explanation

A priority queue organizes elements by their priority, allowing quick access to the highest or lowest priority element. This distinguishes it from other data structures like stacks or simple queues that do not consider priority.

Describe the process of building a max heap from an array.

• You can only build a max heap from a binary tree.

• Building a max heap requires sorting the array first.

• The process of building a max heap from an array involves heapifying from the last non-leaf node up to the root.

• The process starts from the root and goes down to the leaves.

Answer explanation

To build a max heap from an array, start heapifying from the last non-leaf node up to the root. This ensures that each subtree satisfies the max heap property, resulting in a valid max heap structure.

What is the difference between a max heap and a min heap?

• Both max heaps and min heaps allow access to the maximum element only.

• A max heap allows access to the maximum element, while a min heap allows access to the minimum element.

• A max heap allows access to the minimum element, while a min heap allows access to the maximum element.

• A max heap is a complete binary tree, while a min heap is not necessarily a complete binary tree.

Answer explanation

A max heap prioritizes the maximum element, allowing quick access to it, while a min heap prioritizes the minimum element for quick access. This distinction is key in understanding their respective structures and uses.

How do you delete the maximum element from a max heap?

• Swap the root with the second largest element and remove the root.

• Replace the root with the last element, remove the last element, and heapify.

• Remove the root and keep the last element as the new root.

• Delete the last element without any changes to the root.

Answer explanation

To delete the maximum element in a max heap, replace the root with the last element, remove the last element, and then heapify to maintain the heap property. This ensures the new root is correctly positioned.