Made Easy Test Series:Programming and DS

Question

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?

Comments

i think Heap is generally preferred for priority queue implementation . it gives better performance other thamn linked list and array.

---

IN Array:

1.  ARRAY: 

  i) insert operation can be implemented by adding an item at end of array in O(1) time .

 ii) getHighestPriority  operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.

iii) deleteHighestPriority  operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

2.Linked List:

 time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority can be more efficient as we don’t have to move items.

3.Heap:

  i)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.
ii) fibanooci heap  insert() and getHighestPriority can be implemented in O(1) amortized time and deleteHighestPriority can be implemented in O(Logn) amortized time.

Hence Heap is generally preferred for priority queue implementation .

---

in wiki also told as heap, but ans is sorted array

---

no, ans is something else

---

maa'm  how sorted array is corret answer?/

---

I think it is because in sorted array, we can do insertion , deletion, searching in $O\left (  logn \right )$ time.

but heap need build heap method which is $O(n)$ time

---

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

---

@Anuj Mishra

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

---

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.

Answer 1

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.

Comments

ok :)
is that mean heap can be answer too?

---

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?

---

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?

Answer 2

                                   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

Comments

no, I donot think it is correct

because sorted array insertion deletion cannot be $O(n)$

---

and also tell me how priority queue operating on sorted array

Answer 3

Answer is heap because heap takes minimum time in Enqueue and Dequeue as O(logn)

Answer 4

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/