Skip to main content

Return to Question

Post Reopened by Caleth, Richard, tux3, CommunityBot, Jim Mischel
Improved formatting, grammar
Source Link
Ivaylo Valchev
Ivaylo Valchev
  • 10.4k
  • 6
  • 60
  • 86

Why priority_queue is priority_queue implemented using heaps when without using heaps too we can implement it with just vectors.

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion  : We can use binary search  . Complexity O(logN)

For deletion  : Here also we can use binary search. Complexity O(logN)

For top element  : O(1)

In additonaddition, we can have access kth maximum element in just O(1) time which is not the case with heaps  .

Then  , why do we use heaps for implementing priority queues.?

Why priority_queue is implemented using heaps when without using heaps too we can implement it with just vectors

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion  : We can use binary search  . Complexity O(logN)

For deletion  : Here also we can use binary search. Complexity O(logN)

For top element  : O(1)

In additon we can have access kth maximum element in just O(1) time which is not the case with heaps  .

Then  , why we use heaps for implementing priority queues.

Why is priority_queue implemented using heaps when without using heaps too we can implement it with just vectors.

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion: We can use binary search. Complexity O(logN)

For deletion: Here also we can use binary search. Complexity O(logN)

For top element: O(1)

In addition, we can have access kth maximum element in just O(1) time which is not the case with heaps.

Then, why do we use heaps for implementing priority queues?

Improved formatting, grammar
Source Link
edit approved May 3, 2018 at 12:37
Keren Caelen
edit approved May 3, 2018 at 12:37
Keren Caelen
  • 1.5k
  • 3
  • 18
  • 40

Why priority_queue is implemented using heaps when without using heaps too we can implement it with just vectors

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion : We can use binary search . Complexity O(logN)Complexity O(logN)

For deltiondeletion : Here also we can use binary search. Complexity O(logN)Complexity O(logN)

For top element : O(1)O(1)

In additon we can have access kth maximum element in just O(1)O(1) time which is not the case with heaps .

Then , why we use heaps for implementing priority queues.

Why priority_queue is implemented using heaps when without using heaps too we can implement it with just vectors

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion : We can use binary search . Complexity O(logN)

For deltion : Here also we can use binary search. Complexity O(logN)

For top element : O(1)

In additon we can have access kth maximum element in just O(1) time which is not the case with heaps .

Then , why we use heaps for implementing priority queues.

Why priority_queue is implemented using heaps when without using heaps too we can implement it with just vectors

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion : We can use binary search . Complexity O(logN)

For deletion : Here also we can use binary search. Complexity O(logN)

For top element : O(1)

In additon we can have access kth maximum element in just O(1) time which is not the case with heaps .

Then , why we use heaps for implementing priority queues.

Post Closed as "Needs details or clarity" by CommunityBot, Nick is tired, Rob, Michał Turczyn
Source Link
prashant shishodia
prashant shishodia
  • 39
  • 6

Why priority queue is implemented using heaps when we can implement it using just vector more efficiently

Why priority_queue is implemented using heaps when without using heaps too we can implement it with just vectors

Suppose we use vector as a queue and keep the elements in decreasing order. We can use this as priority queue.

For insertion : We can use binary search . Complexity O(logN)

For deltion : Here also we can use binary search. Complexity O(logN)

For top element : O(1)

In additon we can have access kth maximum element in just O(1) time which is not the case with heaps .

Then , why we use heaps for implementing priority queues.