今天在看a*寻路的代码时看到了pop_heap的操作，之前都是用优先权队列来做类似的事，所以补一下知识
vector<int> v;
make_heap(v.begin(),v.end());///将当前vector构造成一个最大堆
vector不能从头部插入或删除元素，所以删除最大元素操作：
pop_heap(v.begin(),v.end());///第一步，将最大元素放到末尾，
v.pop_back();///第二步弹出最大元素
插入一个元素
v.push_back(x);
push_heap(v.begin(),v.end());///执行这一步时，之前的vector必须时保持堆形态，如果不是堆形态会报错
sort_heap(v.begin(),v.end());///堆排序，vecot必须时堆形态
总结：make_heap构造一个堆，其他堆操作都需要保证vector是堆形态
堆的应用：动态计算一个序列的中位数
维护一个最大堆，一个最小堆，当插入一个元素时，插入到元素个数较少的那个堆中
与优先权队列的效率比较：
执行1000w次插入和删除操作
优先权队列：33s
vector+heap:37s
网友评论