DSA Quiz 11
What is the overall structure of a heap? - answer Elements are stored first on the left,
and leaves are only on the last and second to last layer. For min heaps, children's
values are >= their parent's values. For max heaps, children's values are <= their
parent's values
In a list, what is the index of the root? - answer list[0]
In a list, what is the index of a node's left child? - answer2 * current index
In a list, what is the index of a node's right child? - answer (2 * current index) + 1
In a list, what is the index of a node's parent? – answer Math. Floor(current index / 2)
Why is it preferred to use an array for a binary heap? - answer Saves space (No need
to store pointers, arrays are more compact in memory), Saves time (*2 /2 operations are
faster than dereferences), Parent is easy to locate (free parent "pointer")
What does the push(T data) method do in binary heaps? - answer Adds data to the
heap
What does the poll() method do in binary heaps? - answer Remove next priority item in
the heap
What does the peek() method do in binary heaps? - answerReturn the value of the root
What is the time complexity of push? - answerworst: O(log n) average: O(1)
What is the pseudocode of push? - answer-Add element to the bottom level of the heap
while maintaining the shape property,
-Compare value of element with parent value, if it's in correct order, stop.
- If not in correct order, swap with parent and keep comparing until in correct place (This
is known as percolateUp)
How many of the elements are leaves? - answerHalf
What is the average number of checks for per insert for push? - answer2
What is the pseudocode of poll in a heap? - answer-Remove the root
- Make the last element in the 1D array the new root
What is the overall structure of a heap? - answer Elements are stored first on the left,
and leaves are only on the last and second to last layer. For min heaps, children's
values are >= their parent's values. For max heaps, children's values are <= their
parent's values
In a list, what is the index of the root? - answer list[0]
In a list, what is the index of a node's left child? - answer2 * current index
In a list, what is the index of a node's right child? - answer (2 * current index) + 1
In a list, what is the index of a node's parent? – answer Math. Floor(current index / 2)
Why is it preferred to use an array for a binary heap? - answer Saves space (No need
to store pointers, arrays are more compact in memory), Saves time (*2 /2 operations are
faster than dereferences), Parent is easy to locate (free parent "pointer")
What does the push(T data) method do in binary heaps? - answer Adds data to the
heap
What does the poll() method do in binary heaps? - answer Remove next priority item in
the heap
What does the peek() method do in binary heaps? - answerReturn the value of the root
What is the time complexity of push? - answerworst: O(log n) average: O(1)
What is the pseudocode of push? - answer-Add element to the bottom level of the heap
while maintaining the shape property,
-Compare value of element with parent value, if it's in correct order, stop.
- If not in correct order, swap with parent and keep comparing until in correct place (This
is known as percolateUp)
How many of the elements are leaves? - answerHalf
What is the average number of checks for per insert for push? - answer2
What is the pseudocode of poll in a heap? - answer-Remove the root
- Make the last element in the 1D array the new root
