I 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 ?
- [algogeeks] [ counting sort ideea ] ed.thyme