An efficient data structure supporting Insert, Delete, and MostFrequent
In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$  amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, you may implement your priority queue in $o(\log n)$. Indeed, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $ and $\mathcal{O}(1) $ time for the findMin operation. Thorup proved that

If we can sort $n$ keys in time $S(n)$ per key, then we can implement a priority queue supporting find-min in constant time and updates (insert and delete) in $S(n)$ time.

See M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Since we can sort in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space, as shown by

Y. Han and M. Thorup. Integer sorting in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space. in Proc. FOCS 2002

the bound is proved.