patternMinor
Why is a heap better than a linked list for implementation of a priority queue?
Viewed 0 times
prioritywhyimplementationthanbetterheapforlistlinkedqueue
Problem
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?
Why is it better to have log-n for both than n for one and constant time for the other?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#102828, answer score: 3
Revisions (0)
No revisions yet.