Question 1

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

A minheap is defined exactly by the property that each node is less than or equal to its children, making it a complete binary tree where the smallest element is always at the root.

Question 2

A minheap stores its smallest element at the ________ of the binary tree.

Accepted Answer

In a minheap, the smallest element is always stored at the root of the binary tree.

Question 3

Both children of the root of a minheap are _________.

Accepted Answer

In a minheap, the root is always the smallest element, and its children are always greater than or equal to it. Therefore, both children of the root of a minheap are also minheaps.

Question 4

The __________ 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 is typically used to add an element to a heap while maintaining its properties.

Question 5

Since a heap is a complete 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

The statement describes a characteristic of a complete tree, where every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This property ensures a unique location for new node insertions, making it applicable to both minheaps and maxheaps, as they are both complete trees by definition.

Question 6

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, tracking the position of the last leaf is crucial for maintaining the complete binary tree property, which ensures that all levels of the tree are fully filled except possibly the last, which is filled from left to right. This facilitates efficient operations such as insertion and deletion.

Question 7

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

Accepted Answer

In a complete binary tree, if you need to maintain the completeness of the tree while replacing an element, the only valid element to replace without disturbing the structure is the root. This is because replacing the root with the element stored in the last leaf allows for easy reorganization to maintain the tree's complete structure.

Question 8

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

Accepted Answer

A minheap is a binary tree-based data structure that efficiently supports the operations of a priority queue, such as insert, find the minimum, and remove the minimum.

Question 9

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

In a heap, each node needs to store a pointer to its parent to allow traversal up the tree after an insertion. This is essential for maintaining the heap property by comparing newly inserted elements with their parents and possibly swapping them to ensure the heap's structural and order properties are preserved.

Question 10

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 11

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 12

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

Accepted Answer

The removeMin operation for a binary heap, whether implemented using an array or a linked structure, is O(log n) because it typically involves removing the root element and then reheapifying the structure, which requires traversing down the height of the tree. The height of a balanced binary heap is O(log n).

Question 13

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

Accepted Answer

The heapSort method involves building a heap from the list of elements and then repeatedly removing the maximum element from the heap and adding it to the end of the sorted list until the heap is empty. This process effectively sorts the list.

Question 14

Heap sort is O(________).

Accepted Answer

Heap sort has a time complexity of O(n log n) because it involves building a heap from the input data, which takes O(n) time, and then repeatedly extracting the maximum element from the heap and rebuilding the heap, each of which takes O(log n) time, for a total of n elements.

Question 15

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

Accepted Answer

The answer of A minheap is a complete ______ tree...

Question 16

A ______ stores its smallest element at the root of the binary tree.

Accepted Answer

The answer of A ______ stores its smallest element at...

Question 17

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

Accepted Answer

The answer of The addElement method adds a given ______...

Question 18

Since a heap is a ______ 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

The answer of Since a heap is a ______ tree,...

Question 19

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

Accepted Answer

The answer of Typically, in ______ implementations, we keep track...

Question 20

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

Accepted Answer

The answer of To maintain the ______ of the tree,...

Quiz 11: Binary Search Trees