Re: [ counting sort ideea... ]

"ed.thyme" :
> have a data structure and also i have 3 basic operation, find_min,
> delete_min and insert .
> A sequence of m operation could look like this:
> insert,insert,insert,delete,find_min....etc..
> Any M operations of these, should have O(M+k) complexity( O(m+k) -worst
>
> case).
> My ideea is to have a sorted array, so the minimum would be on the
> first position so the complexity would be O(1) for find_min and delete.
>
> But i don't know what to do with insert . Any clues ?

what is k ? constant ? so O(n+k)=O(n)?

if
n x (insert) is O(n), and
n x (find_min,delete_min) is O(2n)
then u can sort your data in O(3n) time... so i it's not possible (in
general case)

greets
Marcin


.