[Tutor] question
Joel Goldstick
joel.goldstick at gmail.com
Tue Mar 24 07:36:51 EDT 2020
On Tue, Mar 24, 2020 at 5:58 AM "Lea Köppel" <lea.koeppel at gmx.net> wrote:
>
> 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
>
>
Welcome Lea. This is a group of python interested people of varying
levels of expertise. A play to ask questions about code, and how
python works. Its a voluntary thing.
That said, your question looks like a homework assignment. People
here don't provide answers to homework assignments, but often provide
guidance or help to get you started. Since your problem is not a
coding question, and really isn't specific to python. It is more of
what I would call a 'computer science question'.
>
>
>
> 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.
> _______________________________________________
> Tutor maillist - Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
--
Joel Goldstick
http://joelgoldstick.com/blog
http://cc-baseballstats.info/stats/birthdays
More information about the Tutor
mailing list