#include <iostream> #include <vector> using namespace std; class bigheap{ //大顶堆 public: vector<int> heap; //堆的底层:数组 //大顶堆插入一个数:先将要插入的数存放在堆的最后(即容器的末尾,下标为index), // 再与其父节点(下标为(index-1)/2)的值进行比较,如果大于父节点的值,则交换两者的位置, //直到循环结束;否则,位置不变,退出循环。 void insert(int val){ heap.push_back(val); int index=heap.size()-1; int father=(index-1)/2; while(index>0){ if(heap[index]>heap[father]){ swap(heap[index],heap[father]); index=father; father=(index-1)/2; } else break; } } void swap(int &val1,int &val2){ int temp=val1; val1=val2; val2=temp; } //大顶堆的删除操作:堆只能删除顶部元素。 //首先删除大顶堆的顶部元素,然后将大顶堆的最后一个元素放在顶部,再依次与它大的孩子节点的值进行比较, //如果小于大的孩子节点的值,则与这个大的孩子节点交换位置,如此直到循环结束; //否则,位置不变,退出循环 void pop(){ heap[0]=heap.back(); heap.pop_back(); int max_index=heap.size()-1; int index=0; int lchild; int rchild; while(index<max_index){ lchild=index*2+1; rchild=index*2+2; if(lchild>max_index) break; else if(rchild>max_index){ if(heap[index]<heap[lchild]){ swap(heap[index],heap[lchild]); index=lchild; } else break; } else{ int bigger=heap[lchild]>=heap[rchild]?lchild:rchild; if(heap[index]<heap[bigger]){ swap(heap[index],heap[bigger]); index=bigger; } else break; } } } }; int main(){ bigheap heap2; for(int i=0;i<8;i++){ heap2.insert(i); } for(int i:heap2.heap){ cout<<i; } cout<<endl; heap2.pop(); for(int i:heap2.heap){ cout<<i; } cout<<endl; return 0; };