Searching is for the highest priority element
Linked List(Single link list) : Insertion O(1), Deletion O(n), Searching O(n)
Heap : Insertion O(logn), Deletion O(logn),Searching O(1)
Sorted array : Insertion O(n), Deletion O(1), Searching O(1)
Unsorted array : Insertion O(1), Deletion O(n), Searching O(n)
Heap would be the best choice because as n approaches a very large number say 10^9. Then 2 times O(logn) ( for searching and deletion in heap ) would be negligible to O(n)( insertion in sorted array )