Tree Heaps and Priority Queues Quiz
40 comprehensive questions exploring heap data structures — with 16 code examples covering min-heap, max-heap, heapify operations, and priority queue implementations in this cpp quiz.
40 Questions
~80 minutes
1
Question 1
What is a heap data structure?
A
A specialized tree-based data structure that satisfies the heap property, where each node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children, allowing efficient access to the highest or lowest priority element
B
A linear data structure like an array
C
A tree where nodes are arranged randomly
D
A structure with no ordering requirements
2
Question 2
In a max-heap, where is the largest element located?
text
Max-heap property: parent >= children
Largest: always at rootA
At the root of the heap, as the heap property ensures the maximum element is always accessible at the top of the structure for immediate priority access
B
At a leaf node
C
In the middle of the heap
D
At any random position
3
Question 3
What is the time complexity of heap insertion?
A
O(log n) due to the heapify-up process that compares and swaps elements along the path from the inserted leaf to the root, maintaining the heap property with logarithmic comparisons
B
O(n)
C
O(1)
D
O(n log n)
4
Question 4
How does heapify maintain the heap property?
text
Heapify compares node with children:
If violation, swap and recurseA
By comparing the current node with its children and recursively swapping with the appropriate child when the heap property is violated, ensuring the subtree rooted at that node satisfies the heap ordering
B
By rearranging all elements randomly
C
By only checking the root node
D
By using linear search
5
Question 5
What is the difference between min-heap and max-heap?
A
Min-heap maintains the minimum element at root with parent ≤ children property, while max-heap maintains the maximum element at root with parent ≥ children property, determining whether the heap supports minimum or maximum priority extraction
B
They are identical structures
C
Min-heap is faster than max-heap
D
Max-heap uses more memory
6
Question 6
In heap deletion (extract-min/max), what happens after removing the root?
text
Extract root: move last element to root
Then heapify down to maintain propertyA
The last element in the heap array is moved to the root position, then heapify-down is performed to restore the heap property by comparing with children and swapping as needed throughout the affected path
B
The heap is rebuilt from scratch
C
All elements are shifted left
D
The root is replaced with a random element
7
Question 7
What is heapify-up used for in heap operations?
A
To maintain the heap property after insertion by comparing the newly added element with its parent and swapping upwards until the heap property is satisfied, ensuring the element bubbles up to its correct position
B
To build the initial heap
C
To delete elements
D
To sort the heap
8
Question 8
How is a heap typically implemented?
cpp
Heap as array:
Parent: i
Left: 2*i+1
Right: 2*i+2A
Using an array where parent-child relationships are maintained through index calculations, with root at index 0 and children at 2*i+1 and 2*i+2, providing efficient access without explicit pointers
B
Using a linked list
C
Using a balanced binary search tree
D
Using a hash table
9
Question 9
What is the worst-case time complexity for building a heap?
A
O(n) using the linear-time heapify algorithm that processes nodes from bottom-up, with each heapify operation taking O(log n) but the total work being bounded by the heap's properties
B
O(n log n)
C
O(log n)
D
O(n²)
10
Question 10
In a priority queue implemented with a heap, what operation has the highest priority?
text
Priority queue operations:
- Insert: add element
- Extract: remove highest priorityA
Extract-min (for min-heap) or extract-max (for max-heap), which removes and returns the highest priority element located at the root, maintaining the priority queue's ability to always access the most important element efficiently
B
Insert operation
C
Peek operation
D
Size check
11
Question 11
What is the heap property?
A
For every node in the heap, the value of the node is greater than or equal to (max-heap) or less than or equal to (min-heap) the values of its children, creating a partial ordering that ensures the highest or lowest priority element is at the root
B
All nodes have the same value
C
The tree is perfectly balanced
D
No duplicate values allowed
12
Question 12
How does heap sort work?
text
Heap sort: build max-heap, then repeatedly
extract max and place at endA
By first building a max-heap from the input array, then repeatedly extracting the maximum element and placing it at the end of the array, gradually sorting the elements in-place with O(n log n) time complexity
B
By using quicksort internally
C
By comparing all elements
D
By using merge sort
13
Question 13
What is the space complexity of heap operations?
A
O(n) for storing the heap elements in an array representation, with O(1) auxiliary space for most operations since heaps can be manipulated in-place without requiring additional data structures beyond the input array
B
O(1)
C
O(log n)
D
O(n log n)
14
Question 14
In heap applications, when would you use a min-heap over a max-heap?
text
Min-heap for:
- Priority queues needing smallest first
- Dijkstra's algorithmA
When you need to prioritize smaller values first, such as in algorithms like Dijkstra's shortest path where you want to always extract the minimum distance node, or in event simulation where earlier events have higher priority
B
When memory is limited
C
When the dataset is small
D
When you need maximum values
15
Question 15
What is the relationship between heap height and performance?
A
Heap operations are O(log n) because the height of a heap with n elements is floor(log2(n)), meaning each operation traverses at most this logarithmic path from root to leaf, determining the asymptotic complexity
B
Height has no impact on performance
C
Taller heaps are faster
D
Shorter heaps are slower
16
Question 16
How does priority queue insertion work in a heap?
cpp
void insert(vector<int>& heap, int val) {
heap.push_back(val);
int i = heap.size() - 1;
while (i > 0 && heap[(i-1)/2] < heap[i]) {
swap(heap[(i-1)/2], heap[i]);
i = (i-1)/2;
}
}A
By adding the element at the end of the array and performing heapify-up to bubble it up to its correct position, comparing with parents and swapping until the heap property is restored throughout the path to the root
B
By inserting at the root
C
By rebuilding the entire heap
D
By using linear search
17
Question 17
What makes heaps suitable for priority queues?
A
The ability to efficiently access and remove the highest priority element in O(log n) time while supporting fast insertions, making heaps ideal for dynamic priority management where priorities can change over time
B
They use less memory than arrays
C
They are easier to implement
D
They support random access
18
Question 18
In heapify-down, what is the process for maintaining heap property?
text
Heapify down: find largest child
If larger than current, swap and continueA
Starting from the current node, compare it with both children to find the largest (max-heap) or smallest (min-heap), swap with that child if the property is violated, and recursively continue down the affected subtree path
B
Only check the root node
C
Swap with a random child
D
Move elements to the top
19
Question 19
What is the advantage of heap over sorted array for priority queues?
A
Heap supports O(log n) insertions while maintaining O(1) access to the highest priority element, whereas sorted array requires O(n) insertions to maintain order, making heap more efficient for dynamic priority queue operations
B
Heap uses less memory
C
Heap is easier to implement
D
Sorted array has slower access
20
Question 20
How does heap support decrease-key operations?
text
Decrease key: update value, heapify up
Since value decreased, may need to bubble upA
By updating the element's value and performing heapify-up if the new value violates the heap property with its parent, ensuring the element moves to its correct position in the priority order after the key modification
B
By rebuilding the heap
C
By removing and reinserting the element
D
Decrease-key is not supported in heaps
21
Question 21
What is the heap condition violated in this structure?
text
5
/ \
7 3
Max-heap: 7 > 5 violates parent >= childA
The left child 7 is greater than its parent 5, violating the max-heap property that requires every parent node to be greater than or equal to its children in a properly constructed heap structure
B
The tree is not complete
C
There are duplicate values
D
The height is wrong
22
Question 22
In which algorithm is heap commonly used?
A
Dijkstra's shortest path algorithm, where a min-heap priority queue efficiently extracts the next closest vertex while updating distances, enabling the algorithm to find optimal paths in weighted graphs with logarithmic time operations
B
Binary search
C
Linear search
D
Hash table operations
23
Question 23
What is the complete binary tree property in heaps?
text
Complete tree: all levels filled except last
Last level filled left to rightA
The heap must be a complete binary tree where all levels are fully filled except possibly the last level, which is filled from left to right, ensuring the array representation has no gaps and maintains efficient space usage
B
All nodes must have two children
C
The tree must be balanced
D
Leaves must be at the same level
24
Question 24
How does heap support k-way merge operations?
A
By maintaining k elements in a heap and repeatedly extracting the minimum element while inserting the next element from each source, efficiently merging multiple sorted sequences with logarithmic time for each extraction and insertion operation
B
By using linear search
C
By sorting all elements first
D
K-way merge is not efficient with heaps
25
Question 25
What is the amortized analysis of heap operations?
text
Each operation O(log n)
But heapify-up/down paths overlapA
Each individual heap operation takes O(log n) time in the worst case, but the amortized cost considers that the total work across a sequence of operations is efficient due to the limited path lengths and overlapping operations in the heap structure
B
All operations are O(1)
C
Operations get slower over time
D
Amortized cost is O(n)
26
Question 26
In priority queue applications, when is a max-heap preferred?
A
When higher numerical values represent higher priority, such as in scheduling systems where tasks with higher priority numbers should be processed first, or in event simulation where later timestamps have lower priority than earlier ones
B
When memory is the primary concern
C
When the dataset is static
D
When minimum values are needed
27
Question 27
What is the heap's role in Prim's algorithm?
text
Prim's: grow MST by adding minimum edge
Heap extracts next closest vertexA
To efficiently select the next vertex with the minimum edge weight connecting to the growing minimum spanning tree, using the heap to maintain and extract vertices by their current minimum distance to the MST
B
To store the final MST
C
To perform the initial sorting
D
Prim's doesn't use heaps
28
Question 28
How does heap handle duplicate priorities?
A
Duplicates are allowed and handled naturally by the heap property, with elements of equal priority arranged arbitrarily in the heap structure while maintaining the overall ordering for higher and lower priority elements
B
Duplicates are rejected
C
Duplicates replace existing elements
D
Duplicates cause heap corruption
29
Question 29
What is the cache performance of heap operations?
text
Array-based heap: good locality
Operations access nearby elementsA
Generally good due to the array-based implementation where heapify operations access elements that are likely to be in cache, as parent and children indices are numerically close and tend to be stored in contiguous memory locations
B
Poor because of random access
C
Excellent due to pointer chasing
D
Cache performance is irrelevant
30
Question 30
In heap construction, why is bottom-up heapify O(n)?
A
Because the algorithm processes nodes from the bottom of the heap upwards, and the work done at each level decreases geometrically, with lower levels requiring less heapify operations due to their smaller subtree heights, resulting in linear total time
B
Because each element is processed once
C
Because the heap is sorted
D
Because n is small
31
Question 31
What is the significance of heaps in algorithm design?
text
Heaps enable:
- Priority queues O(log n)
- Heap sort O(n log n)
- Graph algorithmsA
Heaps provide the foundation for efficient priority-based algorithms, enabling logarithmic-time priority operations that are crucial for graph algorithms, sorting, and optimization problems requiring dynamic priority management
B
They are the fastest data structure
C
They use the least memory
D
They are easiest to implement
32
Question 32
How does heap differ from binary search tree for priority queues?
A
Heap provides O(log n) insertion and O(1) find-min/max with weaker ordering guarantees, while BST provides O(log n) for all operations but maintains complete ordering, making heap more suitable for pure priority queue usage
B
They are identical in functionality
C
Heap is slower than BST
D
BST doesn't support priorities
33
Question 33
What is the heap's role in median maintenance algorithms?
text
Two heaps: max-heap for lower half
Min-heap for upper halfA
By using two heaps - a max-heap for the lower half of values and a min-heap for the upper half - the median can be efficiently maintained and accessed in logarithmic time for insertions while keeping the heaps balanced in size
B
Single heap for all values
C
Heap doesn't help with medians
D
Using sorted arrays instead
34
Question 34
How does heap support sliding window maximum problems?
A
By maintaining a max-heap of elements in the current window, with each heap entry storing both value and index to handle window sliding, enabling efficient maximum queries while removing expired elements as the window moves
B
By using linear search
C
By sorting the window each time
D
Sliding window is not efficient with heaps
35
Question 35
What is the heap property in terms of array indices?
cpp
For max-heap: heap[i] >= heap[2*i+1] && heap[i] >= heap[2*i+2]A
For any index i, the element at heap[i] must be greater than or equal to (max-heap) or less than or equal to (min-heap) the elements at indices 2*i+1 and 2*i+2, representing the parent-child relationships in the array-based heap implementation
B
All elements must be equal
C
Elements must be in sorted order
D
No relationship between indices
36
Question 36
In heap applications, what is the trade-off with binary search trees?
A
Heap provides faster priority access with weaker ordering, while BST maintains complete ordering at the cost of slightly slower operations, requiring careful choice based on whether full ordering or just priority access is needed
B
Heap is always better
C
BST is always better
D
They have identical performance
37
Question 37
How does heap support multi-level priority systems?
text
Priority as pair: (level, value)
Heap compares first by level, then valueA
By storing priority as composite values where primary priority (like urgency level) is compared first, then secondary priorities (like timestamps) are used as tie-breakers, allowing the heap to maintain complex priority hierarchies efficiently
B
By using separate heaps
C
By sorting all elements
D
Multi-level priorities are not supported
38
Question 38
What makes heap suitable for event-driven simulation?
A
The ability to efficiently schedule and process events in chronological order using a min-heap priority queue, where event times serve as priorities and the heap ensures the next event is always accessible for processing in the simulation timeline
B
Fast random access
C
Memory efficiency only
D
Event simulation doesn't use heaps
39
Question 39
In heap construction, what is the advantage of Floyd's algorithm?
text
Floyd's: start from bottom, heapify each subtree
O(n) time, better than repeated insertionsA
It builds the heap in linear time by starting from the bottom of the tree and performing heapify operations on each subtree, avoiding the O(n log n) cost of repeated insertions while achieving the same result more efficiently
B
It uses less memory
C
It creates a sorted array
D
Floyd's algorithm is slower
40
Question 40
Considering heap operations and their applications in algorithm design, which fundamental property makes heaps essential for efficient priority-based computations despite their structural simplicity?
A
The combination of array-based implementation with heap property guarantees O(1) access to highest priority elements and O(log n) modifications, enabling efficient priority queue operations that are crucial for graph algorithms, sorting, and dynamic optimization problems requiring frequent priority updates
B
Guaranteed O(log n) performance always
C
Minimal memory requirements
D
Ease of implementation only