search

roarin-roran / Sorting

0 stars 0 forks source link

tournament tree (winner tree) IPQ #13

Open roarin-roran opened 2 years ago

roarin-roran commented 2 years ago

replace the dummy IPQ with a tournament tree, which should make its own empy runs if necessary (so the IPQ should accept less than k runs, but may not merge more than k runs)

roarin-roran commented 2 years ago

done :D no empty runs necessary, no powers of 2 either. I skipped straight to a list based implementation to keep it light

roarin-roran commented 2 years ago

what was implemented seems a little different from a tournament tree - based on feedback, have renamed it to hear - this still needs doing

roarin-roran commented 2 years ago

correction - what I implemented was a restricted binary heap based ipq (loser oriented tournament tree). it's got a non-optimal init method, but it's a valid choice for a big O optimal ipq when that's corrected.

it'd be cool to have a tournament tree (winner tree) to run experiments on - but this is done. removing it from its sprint and labelling it small fry, with a new name