The Gateway to Computer Science Excellence
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 (119k points) | 120 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,833 questions
57,688 answers
107,248 users