Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.
Why is it better to have log-n for both than n for one and constant time for the other?
0
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
It only really matters in the limit: for small sizes, the difference isn't really important.
But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is asymptotically faster than $O(n) + O(1) = O(n)$.
