词条 | 二叉堆 |
释义 | 二叉堆是一种特殊的堆,二叉堆是完全二元树或者是近似完全二元树。二叉堆满足堆特性:父结点的键值总是大于或等于任何一个子节点的键值。二叉堆一般用数组来表示。 存储二叉堆一般用数组来表示。例如,根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2。因此,第0个位置的子节点在1和2,1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。 如下图的两个堆: 1 11 / \\ / \\ 2 3 9 10 / \\ / \\ / \\ / \\ 4 5 6 7 5 6 7 8 / \\ / \\ / \\ / \\ 8 9 10 11 1 2 3 4 将这两个堆保存在以1开始的数组中: 位置: 1 2 3 4 5 6 7 8 9 10 11 左图: 1 2 3 4 5 6 7 8 9 10 11 右图: 11 9 10 5 6 7 8 1 2 3 4 基本操作概述在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。 形式上看,它从顶点开始,每个节点有两个子节点,每个子节点又各自有自己的两个子节点;数值上看,每个节点的两个子节点都比它大或和它相等。 要求在二叉堆里我们要求: * 最小的元素在顶端 * 每个元素都比它的父节点大,或者和父节点相等。 只要满足这两个条件,其他的元素怎么排都行。如上面的例子,最小的元素10在最顶端,第二小的元素20在10的下面,但是第三小的元素24在20的下面,也就是第三层,更大的30反而在第二层。 这样一“堆”东西我们在程序中怎么用呢?幸运的是,二叉堆可以用一个简单的一维数组来存储,如下图所示。 假设一个元素的位置是n(第一个元素的位置为1,而不是通常数组的第一个索引0),那么它两个子节点分别是 n × 2 和 n × 2 + 1 ,父节点是n除以2取整。比如第3个元素(例中是20)的两个子节点位置是6和11,父节点位置是1。 三种操作对于二叉堆我们通常有三种操作:添加、删除和修改元素: * 添加元素 首先把要添加的元素加到数组的末尾,然后和它的父节点(位置为当前位置除以2取整,比如第4个元素的父节点位置是2,第7个元素的父节点位置是3)比较,如果新元素比父节点元素小则交换这两个元素,然后再和新位置的父节点比较,直到它的父节点不再比它大,或者已经到达顶端,及第1的位置。 * 删除元素 删除元素的过程类似,只不过添加元素是“向上冒”,而删除元素是“向下沉”:删除位置1的元素,把最后一个元素移到最前面,然后和它的两个子节点比较,如果较小的子节点比它小就将它们交换,直到两个子节点都比它大。 * 修改元素 和添加元素完全一样的“向上冒”过程,只是要注意被修改的元素在二叉堆中的位置。 可以看出,使用二叉堆只需很少的几步就可以完成排序,很大程度上提高了寻路速度。 具体实现在C++的STL中提供了优先队列,定义方式为priority_queue<int> priq;默认为每一次弹出队列中最大的元素,与二叉堆性质相似,很多时候可以直接当作二叉堆使用。 当然,也可以直接自己写一个C++的类模板,以下是完整代码: #include <cstdio> const int MAXN = 11111; int n, a[MAXN], ans = 0; //以下两个是自定义校验函数,mincmp是小根堆所需要的,而maxcmp就是大根堆所需要的了, inline bool mincmp(const int &x, const int &y) { return x < y; } inline bool maxcmp(const int &x, const int &y) { return x > y; } //定义,第一个关键字为堆的大小,第二关键字为自定义校验类型 template <int N, bool (*cmp)(const int &X, const int &Y) > class Heap { private: int a[N], n;//n表示当前元素的个数,同时也是最后一个元素的下一个指针 public: inline Heap() { clear(); } inline void clear() { n = 0; }//清空 inline void push(int x)//插入操作 { int i; n++;//元素个数相加 for(i = n - 1; i > 0; i = (i - 1) >> 1)//把这个元素和根节点比较并交换 { if(cmp(x, a[(i - 1) >> 1])) a[i] = a[(i - 1) >> 1]; else break; } a[i] = x; } inline void pop()//弹出操作,如果需要在弹出的同时返回总根节点,把void改成int,并加上下面的两行被注释部分 { int tmp, i; n--; //int x = a[0]; for(i = 0; (i << 1) + 1 < n; i = tmp) { //比较左右子树中更优的一个交换(对于小根堆就是较小的那个,大根堆不解释……) tmp = ((i << 1) + 2 < n && cmp(a[(i << 1) + 2], a[(i << 1) + 1])) ? (i << 1) + 2 : (i << 1) + 1; if(cmp(a[tmp], a[n])) a[i] = a[tmp]; else break; } a[i] = a[n]; //return x; } inline int top() { return a[0]; }//返回堆顶元素 inline bool empty() { return !n; }//判断堆是否为空 }; Heap< MAXN, maxcmp > h;//定义一个堆,这里定义的是大根堆,如果要使用小根堆,把第二关键字换成上面的mincmp就可以了 int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", a + i); h.push(a[i]);//压入堆中 } for (int i = 1; i <= n; i++) { printf("%d ", h.top());//从大到小输出 h.pop(); } return 0; } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。