The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Is priority queue work efficiently with sorted array than unsorted array and heap for insertion and deletion operation? Then why do we apply priority queue in heap specially
in DS by Veteran (115k points) | 75 views
Heap : Insertion O(logn), Deletion O(logn)

Sorted array : Insertion O(n), Deletion O(1)

Unsorted array : Insertion O(1), Deletion O(n)

As we are implementing priority queue we will insert and remove the highest priority element, not any random element and searching for any random element is of least concern as we care only about the highest priority, so heap will be best suited for this purpose.

That's what i think.
How is deletion in sorted array O(1)? After the element is deleted , don't we need to shift all elements to fill the gap caused due to deletion?

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,276 answers
86,086 users