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

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

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 Like

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

1 Like

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

Yup! You are right…

so shouldn’t we going down?

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