public inbox for [email protected]
help / color / mirror / Atom feedFrom: =?utf-8?B?Y2NhNTUwNw==?= <[email protected]>
To: =?utf-8?B?Sm9obiBOYXlsb3I=?= <[email protected]>
To: =?utf-8?B?U2FtaSBJbXNlaWg=?= <[email protected]>
Cc: =?utf-8?B?SGVpa2tpIExpbm5ha2FuZ2Fz?= <[email protected]>
Cc: =?utf-8?B?cGdzcWwtaGFja2Vycw==?= <[email protected]>
Subject: Re: Support loser tree for k-way merge
Date: Thu, 4 Dec 2025 14:11:29 +0800
Message-ID: <[email protected]> (raw)
In-Reply-To: <CANWCAZYKgc4xFbBXtePw_XY+a+Ao_-CxZ+Z8YWSrK2B1HqtdWg@mail.gmail.com>
References: <[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<CAA5RZ0u=WDa-v+8Y_yE4WeRS8VtmcmQGuWVjZFCqZcXx-hEP3w@mail.gmail.com>
<CANWCAZYKgc4xFbBXtePw_XY+a+Ao_-CxZ+Z8YWSrK2B1HqtdWg@mail.gmail.com>
Hi,
I summarized the number of comparisons needed for different 'k':
k = 2, heap: 1, loser tree: 1
k = 3, heap: 2, loser tree: [1, 2]
k = 4, heap: [2, 3], loser tree: 2
k = 5, heap: [2, 4], loser tree: [2, 3]
So if k < 5, the loser tree is never worse than the heap for any input data.
Thoughts?
--
Regards,
ChangAo Chen
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: Support loser tree for k-way merge
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox