【数据结构】优先队列类实现(int)

tech2022-08-01  177

class big_heap_int{ private: vector<int>heap; void down(int x){ int s=x*2; while(x<heap.size()-1){ if(heap[s]<heap[s+1]){ ++s; } if(heap[x]<heap[s]){ swap(heap[x],heap[s]); x=s,s=2*x; } else break; } } void up(int x){ while(x>1){ int fa=x/2; if(heap[x]>heap[fa]){ swap(heap[x],heap[fa]); x=fa; }else{ break; } } } public: big_heap_int(){heap.push_back(0);}; ~big_heap_int(){}; void push(int x){ heap.push_back(x); up(heap.size()-1); } void pop(){ heap[1]=*(heap.end()-1); heap.pop_back(); down(1); } int top(){ return heap[1]; } };

 

最新回复(0)