STL Sample[make_heap]

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

struct Node 
{
    int x,y;
    Node(int a = 0,int b = 0):x(a),y(b){}
    	
    bool operator <(const Node& n)
    {
        if (x == n.x)
            return y > n.y ;
        return x > n.x ;
    }	    
};
typedef struct Node SNode;

struct NodeComparator
{
    bool operator()(const Node* nl,const Node* nr)
    {
        if (nl->x == nr->x)
            return nl->y > nr->y;
        return nl->x > nr->x;
    }
};
typedef struct NodeComparator SNodeComparator;

struct NodeFinder
{
	 int x ;
	 int y ;
	 NodeFinder(int a,int b):x(a),y(b){}
	 
	 //此处不能使用const SNode&
	 bool operator()(const SNode* pNode) const
	 {
	 	    return pNode->x == x && pNode->y == y ;
	 }
};
typedef struct NodeFinder SNodeFinder;

int main(int argc, char* argv[])
{
	  deque<SNode* > q;
	  
    q.push_back(new SNode(10,12));
    q.push_back(new SNode(15,12));
    q.push_back(new SNode(20,12));
    q.push_back(new SNode(35,12));
    q.push_back(new SNode(25,12));
    q.push_back(new SNode(10,22));
    
    NodeComparator nodeComparator;
        
    std::cout << "make heap" <<std::endl;
    make_heap(q.begin(),q.end(),nodeComparator);
    cout << "front " << q.front()->x << "  "<<q.front()->y <<endl;
        
    for (unsigned int i = 0; i< q.size(); i++)
    	 cout << q[i]->x <<"   "<< q[i]->y << endl;    		
    		
    std::cout << "pop heap" <<std::endl;
    pop_heap(q.begin(),q.end(),nodeComparator);
    q.pop_front();
    for(unsigned int i = 0; i< q.size(); i++)
    	 std::cout << q[i]->x <<"   "<< q[i]->y << std::endl;
    
    deque<SNode* >::iterator it = find_if(q.begin(),q.end(),SNodeFinder(20,12));
    if(it != q.end())
    {
    	  q.erase(it);
    	  std::cout << "removed the found node."<<std::endl;
    }
    
    make_heap(q.begin(),q.end(),nodeComparator);
    sort_heap(q.begin(),q.end(),nodeComparator);
    for (unsigned int i = 0; i< q.size(); i++)
    	std::cout << q[i]->x <<"   "<< q[i]->y << std::endl;
    
    std::cout << '\n';
    return 0;
}

  

原文地址:https://www.cnblogs.com/syru/p/3017122.html