3,731 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?

4 Answers

1 votes
1 votes

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
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

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

0 votes
0 votes
2 answers
1
Na462 asked Jan 16, 2019
705 views
void PrintValue(int n) { if (n < 0) return; else { printf(n); printValue( n); printValue(n ); printf(n); } }Output for Print(5) ?
4 votes
4 votes
3 answers
3