Dark Mode

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?

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.

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?

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

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

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/