#include "data_structure/binary_heap.hpp"
#pragma once #include<vector> #include<algorithm> #include<functional> /** * @brief BinaryHeap */ template<typename T,typename F=std::less<T>> struct binary_heap{ int idx=1; struct node{ int idx; T val; node(int idx,T val):idx(idx),val(val){} }; using np=node*; std::vector<np>v; F comp; binary_heap(F comp):v(2,0),comp(comp){} binary_heap():v(2,0),comp(F()){} void __swap(np& s,np& t){ std::swap(s,t); std::swap(s->idx,t->idx); } void up(int k){ while(k>1&&comp(v[k]->val,v[k/2]->val)){ __swap(v[k],v[k/2]); k/=2; } } void down(int k){ while(1){ if(k*2+1<idx&&(comp(v[k*2]->val,v[k]->val)||comp(v[k*2+1]->val,v[k]->val))){ if(comp(v[k*2]->val,v[k*2+1]->val)){ __swap(v[k],v[k*2]); k=k*2; }else{ __swap(v[k],v[k*2+1]); k=k*2+1; } }else if(k*2<idx&&comp(v[k*2]->val,v[k]->val)){ __swap(v[k],v[k*2]); k=k*2; }else{ break; } } } np insert(T val){ if((int)v.size()<=idx+1)v.resize(v.size()*2,0); np res=new node(idx,val); v[idx]=res; up(idx++); return res; } T top(){ return v[1]->val; } void pop(){ __swap(v[1],v[--idx]); down(1); } int size(){ return idx-1; } bool empty(){ return idx==1; } void modify(np t,T val){ t->val=val; up(t->idx); down(t->idx); } };
#line 2 "data_structure/binary_heap.hpp" #include<vector> #include<algorithm> #include<functional> /** * @brief BinaryHeap */ template<typename T,typename F=std::less<T>> struct binary_heap{ int idx=1; struct node{ int idx; T val; node(int idx,T val):idx(idx),val(val){} }; using np=node*; std::vector<np>v; F comp; binary_heap(F comp):v(2,0),comp(comp){} binary_heap():v(2,0),comp(F()){} void __swap(np& s,np& t){ std::swap(s,t); std::swap(s->idx,t->idx); } void up(int k){ while(k>1&&comp(v[k]->val,v[k/2]->val)){ __swap(v[k],v[k/2]); k/=2; } } void down(int k){ while(1){ if(k*2+1<idx&&(comp(v[k*2]->val,v[k]->val)||comp(v[k*2+1]->val,v[k]->val))){ if(comp(v[k*2]->val,v[k*2+1]->val)){ __swap(v[k],v[k*2]); k=k*2; }else{ __swap(v[k],v[k*2+1]); k=k*2+1; } }else if(k*2<idx&&comp(v[k*2]->val,v[k]->val)){ __swap(v[k],v[k*2]); k=k*2; }else{ break; } } } np insert(T val){ if((int)v.size()<=idx+1)v.resize(v.size()*2,0); np res=new node(idx,val); v[idx]=res; up(idx++); return res; } T top(){ return v[1]->val; } void pop(){ __swap(v[1],v[--idx]); down(1); } int size(){ return idx-1; } bool empty(){ return idx==1; } void modify(np t,T val){ t->val=val; up(t->idx); down(t->idx); } };