c++针对特定数据结构创建堆

make_heap

https://en.cppreference.com/w/cpp/algorithm/make_heap

struct ds 
{
	double value; 
	int idx;       
	ds(double v, int index) : value(v), idx(index){}
};
   
// 自定义比较函数   
class CMP {
public:
	bool operator()(const ds& a, const ds& b) {
		return a.value< b.value;
	}
};

std::vector<ds> edgeWeights;
std::make_heap(edgeWeights.begin(), edgeWeights.end(), CMP());  // max heap

while (edgeWeights.size() > 0) {
	std::pop_heap(edgeWeights.begin(), edgeWeights.end(), CMP());
	ds top = edgeWeights.back();
	edgeWeights.pop_back();
	continue; 
}

priority_queue

https://en.cppreference.com/w/cpp/container/priority_queue

struct ds
{
	double value;
	int idx;
	ds(double d, int index) : value(d), idx(index) {}
};

struct CMP : public std::binary_function<ds, ds, bool>
{	
	bool operator()(const ds& _Left, const ds& _Right) const
	{	
		return _Left.value > _Right.value;   // min heap
	}
};
typedef std::priority_queue<ds, std::vector<ds>, CMP > DistancePriorityQueue;

priQueue.push(ds(2.0, 0));

while (!priQueue.empty())
{
	ds di = priQueue.top();
	priQueue.pop();
}