Spending a Million on RISC OS

Your reference, Priority Queues with Binary Heaps, is just what I was looking for. Many thanks.

.. another big problem .. all the data in a linear array.

This is where Lua scores. Its table datatype is internally a cunning mixture of linear arrays and hashes so that extending arrays is optimized. See http://www.lua.org/doc/jucs05.pdf, or even the source code http://www.lua.org/source/5.2/ltable.c .

Offhand I can’t think of any easy solutions to that which won’t end up increasing the time complexity of some of the operations.

I understand that in theory a binary tree, heap or otherwise, is the most efficient method of storing ordered items. However, when dealing with a few¹ items, the expense of maintaining a balanced tree is likely to outweigh the simplicity of an ordered linked list.

As I suggested above, in BASIC a linked list is trivially simple, as it is in assembler.

¹ What is a few? Perhaps a dozen or so timed events in any one application. This may not hold for OS_Call*, though, if it is offering the service to all-comers.

So is there going to be a new bounty “Lottery tickets” ;-)

So is there going to be a new bounty “Lottery tickets” ;-)

What do you think RISC OS General is for…? ;)

What do you think RISC OS General is for…? ;)

Drinks at – insert hostelry of choice – ?

for binary tree , there are algorythm like red/black binary tree, or things like this, who can help to maintain always balanced tree for dynamically sorting big list, but i’m not sure there are lot of implementations of that.

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

Which reminds me!
I don’t drink, but if you’re at the Wakey show again this year, I’ll get a round for you. (That’s a subtle question)

or binary tree , there are algorythm like red/black binary tree

That is interesting, but O(log(n)) for insert delete and read, only indicates a good measure of efficiency for large n. If n is small, the critical factor is the time taken by the the operations. Hence the use of linked lists, which are insert O(n), delete O(1) with a handle, and read first O(1). ;-)