in DS
3,727 views
2 votes
2 votes

Which of the following data structure is efficient to implement priority queue such as insertion ,deletion, searching?

A)Linked List

B)Heap

C)Sorted Array

D)Unsorted Array


How priority queue can work more efficiently in any data structure, other than heap?

in DS
by
3.7k views

4 Comments

In sorted array for deletion and insertion, we have to perform shifting which takes O(n) time
1
1

@Anuj Mishra

I yesterday saw somewhere, deletion will take O(1) time. As because, there is certain priority on elements of queue

0
0
It will be called Extract-Min then which will extract the top element. That way we can do in O(1) time. I guess you're right we delete only max element but what about insertion, that can't be done in O(1) it will take O(n) for shifting also array will need to have dynamic size.
0
0

4 Answers

1 vote
1 vote

Extract from Narsimha Karumanchi which must have made things clear, Someone on Stack Overflow said "Get an algorithms textbook, it is better than random SO questions"

Refer this link @srestha Ma'am , Also sorted array isn't better than heap because logn is much much smaller than n, and also because there are equally large number of insertions, Delete Max and Finds (And 2logn is still way smaller than n)

http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

https://en.wikipedia.org/wiki/Priority_queue#Implementation

 

@srestha ma'am If you first refer Narsimha book, you'll get better explanations and also the right concept, @Gateasp2020 refer textbooks instead of online links (I guess you are not doing so and trust me books are much better ), @yajush mishra first understand the context of the question then answer.

Hope I don't offend anyone, just giving honest advice not criticizing anyone.

edited by

4 Comments

ok :)
is that mean heap can be answer too?
0
0
Where is it mentioned that sorted array is better to implement priority queue, everywhere I read it is mentioned that Heaps are used. Can you provide justification to how you come to this conclusion that sorted array is better here?
0
0
The question asks for "Priority Queue" - assume minimum value is maximum priority. Now, if we use a min-heap we get $O(\log n)$ insertion and deletion. Here, deletion is mostly done for maximum priority (extract-min) and rarely for minimum priority or other values (can be even ignored as they do not consititute necessary priority queue functions). Find is also for maximum priority and can be done in $O(1).$

Now, if we use a sorted array, find will be $O(1)$ -- we search for maximum priority which should be the first value.

Insert will be $O(n)$ because we might need to shift all $n$ elements even if we can find the position in $O(\log n)$ time like in Insertion Sort.

Deletion will be $O(n)$ as we need to shift $n-1$ elements one place.
Min. heap clearly wins rt?
1
1
0 votes
0 votes

                                   linked list           heap               sorted array             unsorted array

insertion                        O(N)                O(log N)              O(N)                         O(1)

deletion                         O(N)                O(log N)               O(N)                        O(N)

searching                      O(N)                  O(N)                  O(log N)                     O(N)

 

judging by this, I have two main contenders heap and unsorted array. If more insertions than deletion then i will pick unsorted array but in general heap should be the answer so option B

2 Comments

no, I donot think it is correct

because sorted array insertion deletion cannot be $O(n)$
0
0
and also tell me how priority queue operating on sorted array
0
0
0 votes
0 votes
Answer is heap because heap takes minimum time in Enqueue and Dequeue as O(logn)
0 votes
0 votes

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.

B is correct option 

for good read

https://www.geeksforgeeks.org/priority-queue-set-1-introduction/

Related questions