小顶堆的C++实现

小顶堆就一个特性，儿子比老子大，应该算是比较好实现的数据结构，一共就两个操作。

插入：插入到树的最后，然后往上升

删除：为了实现方便，普遍的做法是用最后一个node替换堆顶，然后把这个node往下降就行了。

其他如建树，更新等操作都是这两个操作的组合。

代码如下：

</pre><pre name="code" class="cpp">#include <iostream> #include <vector> using namespace std; class MinHeap { private: vector<int> a; public: MinHeap(int nums[], int n)//构造小顶堆 { for (int i=0; i<n; i++) a.push_back(nums[i]); for (int i=a.size()/2-1; i>=0; i--) down(i); } void swap(int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } void up(int i)//上升操作 { int f = (i-1)/2; if (i>0 && a[i]<a[f]) { swap(i, f); up(f); } } void push(int p)//插入点 { a.push_back(p); up(a.size()-1); } void down(int i)//下降操作 { int son = 2*i+1; if (son<a.size()) { if (son+1<a.size() && a[son]>a[son+1]) son++; if (a[i]>a[son]) swap(i, son); down(son); } } int pop()//弹出堆顶 { int result = a[0]; swap(0, a.size()-1); a.pop_back(); down(0); return result; } void show() {//输出堆 for (int i = 0; i < a.size(); i++) { cout << a[i]; } cout << endl; } }; int main() { int a[] = {1,3,4,6,2,5,0,7}; MinHeap* m = new MinHeap(a,8); //测试 m->show(); cout<< m->pop() << endl; m->show(); m->push(0); m->show(); return 0; }

嫌up和down递归效率低的可以改成while~

代码没有严格测试，出错了不要打我啊= =。