Search code examples
c++stlpriority-queue

Compare class for priority queue

When we want a min priority queue, we declare Compare class as std:greater. Which is something like return obj1 > obj2

Could anyone elaborate how does priority queue use it? Apply it in insertion? or use it for "heapify" after pop().

We know in insertion, the new element would float up as much as possible. So If insertion uses greater, then obj1 would be parent ? and obj2 would be new element itself?

Solution

  • I looked up STL source code and get to know how is Compare function used. Below is the link http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm

    keyword: push_heap, sift_up 

    if (Compare(parent, children))
    do the swap