Question 1

Though not a queue at all, a ______ provides an efficient implementation of a priority queue.

Accepted Answer

The answer of Though not a queue at all, a...

Question 2

Because of the requirement that we be able to traverse up the tree after an insertion, it is necessary for the nodes in a heap to store a pointer to their ______.

Accepted Answer

The answer of Because of the requirement that we be...

Question 3

In an array implementation of a binary tree, the root of the tree is in position 0, and for each node n, n's left child is in position ______ and n's right child is in position ______.

Accepted Answer

The answer of In an array implementation of a binary...

Question 4

The addElement operation for both the linked and array implementations is O(______).

Accepted Answer

The answer of The addElement operation for both the linked...

Question 5

The removeMin operation for both the linked and array implementations is O(______)

Accepted Answer

The answer of The removeMin operation for both the linked...

Question 6

The heapSort method consists of adding each of the elements of the list to a ______ and then removing them one at a time. If the heap is a minheap, this results in ______ order. However, if the heap is a maxheap, this results in ______ order.

Accepted Answer

The answer of The heapSort method consists of adding each...

Question 7

Heap sort is O(______).

Accepted Answer

The answer of Heap sort is O(______)....

Question 8

A minheap is a complete binary tree in which each node is less than or equal to both the left child and the right child.

Accepted Answer

In a minheap, the key at each node is less than or equal to the keys of its children, maintaining the min-heap property throughout the structure, which is indeed a complete binary tree.

Question 9

A minheap stores its largest element at the root of the binary tree, and both children of the root of a minheap are also minheaps.

Accepted Answer

A minheap stores its smallest element at the root. Both children of the root are indeed minheaps, but the root itself contains the smallest element, not the largest.

Question 10

The addElement method adds a given Comparable element to the appropriate location in the heap, maintaining both the completeness property and the ordering property of the heap.

Accepted Answer

The addElement method in a heap data structure indeed adds a given Comparable element to the appropriate location, ensuring the heap maintains both its completeness property (every level, except possibly the last, is fully filled and all nodes are as far left as possible) and its ordering property (in a max heap, every parent node is greater than or equal to its child nodes; in a min heap, every parent node is less than or equal to its child nodes).

Question 11

Since a heap is a binary search tree, there is only one correct location for the insertion of a new node, and that is either the next open position from the left at level h or the first position on the left at level h+1 if level h is full.

Accepted Answer

A heap is a specialized tree-based data structure that satisfies the heap property, but it is not a binary search tree. In a binary heap, elements are added based on the heap property (either max-heap or min-heap) and not in a specific order like in a binary search tree. The insertion location is determined by maintaining a complete tree, typically by adding the new element to the next available position at the bottom level from left to right, and then the heap property is restored by "heapifying" if necessary.

Question 12

Typically, in heap implementations, we keep track of the position of the last node or, more precisely, the last leaf in the tree.

Accepted Answer

In heap implementations, keeping track of the position of the last node (or last leaf) is crucial for efficiently performing operations like insertions and deletions, as it helps in maintaining the complete binary tree property.

Question 13

To maintain the completeness of the tree, there is only one valid element to replace the root, and that is the element stored in the first leaf in the tree.

Accepted Answer

In binary search trees, the root can be replaced by either the largest element in the left subtree or the smallest element in the right subtree to maintain the tree's properties, not just the first leaf.

Question 14

Though not a queue at all, a minheap provides an efficient implementation of a priority queue.

Accepted Answer

A minheap organizes elements such that the smallest element can be quickly removed, which aligns with the priority queue's operation of removing the element with the highest priority (in this case, the smallest element), thus providing an efficient implementation.

Question 15

Because of the requirement that we be able to traverse up the tree after an insertion, it is necessary for the nodes in a heap to store a pointer to their parent.

Accepted Answer

A heap is a tree-like data structure that stores data in a way that allows for efficient retrieval of the maximum or minimum value. In order to maintain the heap property, it is necessary for the nodes in a heap to store a pointer to their parent. This allows the heap to be traversed up the tree after an insertion, so that the heap property can be restored.

Question 16

In an array implementation of a binary tree, the root of the tree is in position 0, and for each node n, n's left child is in position 2(n+1) and n's right child is in position 2(n+2).

Accepted Answer

In an array implementation of a binary tree, the root of the tree is indeed in position 0, but for each node n, n's left child is in position 2n+1 and n's right child is in position 2n+2.

Question 17

The addElement operation for both the linked and array implementations is O(n log n).

Accepted Answer

The addElement operation complexity depends on the implementation. For an array, it can be O(1) if there's space or O(n) if it needs resizing. For a linked list, it's typically O(1) if adding at the beginning or end (with a reference to the last node) but O(n) if you need to find a specific position. Neither inherently requires O(n log n), which is more characteristic of operations like sorting.

Question 18

The removeMin operation for both the linked and array implementations is O(log n).

Accepted Answer

The removeMin operation for both the linked and array implementations is O(log n) because it requires traversing the tree to find the minimum value and then removing it.

Question 19

The heapSort method consists of adding each of the elements of the list to a heap and then removing them one at a time.

Accepted Answer

HeapSort works by first building a heap from the input data, then repeatedly extracting the maximum element from the heap and adjusting the heap accordingly until the heap is empty, effectively sorting the data.

Question 20

Heap sort is O(n log n).

Accepted Answer

Heap sort has a time complexity of O(n log n) for both the average and worst-case scenarios because it involves building a heap from the input data and then iteratively removing the largest element from the heap and rebuilding the heap, each operation taking logarithmic time proportional to the height of the heap.

Quiz 11: Binary Search Trees