[Tutor] question
"Lea Köppel"
lea.koeppel at gmx.net
Tue Mar 24 04:42:54 EDT 2020
Dear Madam/Sir of the Python Handbook
I have the task below and would be very grateful if you could answer me. Thank you very much for your efforts.
Sincerely, Lea Köppel
Recall
If a Min-Heap is stored in an array C
with 1-based indices, then for all i the entry C[i] must be smaller than
(or equal to) its two children entries C[2⋅i] and C[2⋅i+1]
.
Concatenating Min-Heaps
Let's look at two Min-Heaps A
and B of size n and m, respectively. We assume that each element of A is
smaller than all the elements of B (formally: ∀i,j:A[i]<B[j]). Now let C
be the array of size n+m which we get as a concatenation of A and B,
meaning that C is given by C[i]=A[i] if i≤n and C[i]=B[i−n]
otherwise.
Question:
Is it clear that C
is a Min-Heap as well? If yes, argue why, otherwise find a counterexample.
More information about the Tutor
mailing list