How to insert and increaseKey in priority queue(min heap) using C++ STL?

general
1

Please say me - How to insert and increaseKey in priority queue(min heap) using C++ STL?

2

Here is the pseudocode for increase-key inpriority queue.(using Max-heaps)

if key < a[i]
   then return error
else
 a[i] = key
 while (i > 1) and a[parent(i)] < a[i]
 swap a[i] with a[parent(i)]
 i <- parent(i)

The pseudo code is for a heap pull. With this approach we can only increase key or we can go towards the root, decreasing key with this approach is not possible.

for min heap I think following should work

 Heap-increase-key(A,i,key)
 {
      if(key<A[i])
          return error;
      A[i]=key;
      while(i>1 and A[i/2]<A[i])
            swap A[i] with A[i/2]
            i=i/2;
 }

Here is a very good video tutorial on [Algorithms lecture 14-- Extract max, increase key and insert key into heap
][1]

Please feel free to edit this answer if you find a problem.
[1]: https://www.youtube.com/watch?v=j5ij59EjPh0

1 Like
3

@only4 in min-heaps element at top has the minimum key,right?

1 Like
4

Yup! You are right…

5

so shouldn’t we going down?

6

I think only higher karma people can edit community wiki post! I still cud not able to edit this post

7

Please comment your edit here. I will then edit my answer.

8

Please say - how to implement using C++ STL?

9

Your question is not clear to us. please specify what do you really wanna ask! As far as i know priority queue follow max heap property such that insertion and deletion takes a log(N) time. So if i m right that you are asking about how to implement this by min heap propert?

1 Like
10

Please say me - How to increase Key value in min heap using C++ STL…

11

In C++, there is no template or data structure that will allow you to increase or decrease the key value. You should implement this by own. Yo can see this article to know how to increase or decrease key value http://quiz.geeksforgeeks.org/binary-heap/