首先来看全然二叉树的定义:
若设二叉树的深度为h,除第 h 层外,其他各层 (1~h-1) 的结点数都达到最大个数,第 h 层全部的结点都连续集中在最左边,这就是全然二叉树。而将一维数组视为全然二叉树书得到的即为堆。
堆效率极高。像十分经常使用的排序算法、Dijkstra算法、Prim算法等都要用堆才干优化,差点儿每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于全然二叉树。
STL中与堆相关的4个函数——建立堆make_heap(),在堆中加入数据push_heap()。在堆中删除数据pop_heap()和堆排序sort_heap():
头文件 #include <algorithm>
以下的_First与_Last为能够随机訪问的迭代器(指针)。_Comp为比較函数(仿函数),其规则——假设函数的第一个參数小于第二个參数应返回true,否则返回false。
建立堆
make_heap(_First, _Last, _Comp)
默认是建立最大堆的。对int类型,能够在第三个參数传入greater<int>()得到最小堆。
在堆中加入数据
push_heap (_First, _Last)
要先在容器中增加数据,再调用push_heap ()
在堆中删除数据
pop_heap(_First, _Last)
要先调用pop_heap()再在容器中删除数据
堆排序
sort_heap(_First, _Last)
排序之后就不再是一个合法的heap了
#include <cstdio> #include <vector> #include <algorithm> #include <functional> using namespace std; void PrintfVectorInt(vector<int> &vet) { for (vector<int>::iterator pos = vet.begin(); pos != vet.end(); pos++) printf("%d ", *pos); putchar(' '); } int main() { const int MAXN = 20; int a[MAXN]; int i; for (i = 0; i < MAXN; ++i) a[i] = rand() % (MAXN * 2); //动态申请vector 并对vector建堆 vector<int> *pvet = new vector<int>(40); pvet->assign(a, a + MAXN); //建堆 make_heap(pvet->begin(), pvet->end()); PrintfVectorInt(*pvet); //增加新数据 先在容器中增加。再调用push_heap() pvet->push_back(25); push_heap(pvet->begin(), pvet->end()); PrintfVectorInt(*pvet); //删除数据 要先调用pop_heap(),再在容器中删除 pop_heap(pvet->begin(), pvet->end()); pvet->pop_back(); pop_heap(pvet->begin(), pvet->end()); pvet->pop_back(); PrintfVectorInt(*pvet); //堆排序 sort_heap(pvet->begin(), pvet->end()); PrintfVectorInt(*pvet); delete pvet; return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。