【数据结构】满二叉树、完全二叉树、堆的概念回顾，堆和堆排序的算法实现

2024-07-17 10:18| 来源: 网络整理| 查看: 265

本来只想整理两个内容：

无映射关系的堆排序（eg.堆排序）有映射关系的堆排序（eg.模拟堆）

但是在实现过程中，因为堆的本质是完全二叉树，所以有些地方需要结合完全二叉树的性质来理解。而完全二叉树又是根据满二叉树定义的，所以先回顾一下满二叉树和完全二叉树的基本概念及性质。

1 基本概念及相关性质 1.1 满二叉树

定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2k - 1 ，则它就是满二叉树。注：满二叉树的概念国内外定义是不同的1，我们按国内的定义来。

1.2 完全二叉树 1.2.1 定义

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。在这里插入图片描述

1.2.2 性质

给出完全二叉树的性质是便于理解后面的堆，其中：性质5在后面的代码中用到的最多，性质4略有涉及。我们假定树的深数k >= 1，则完全二叉树满足以下性质2：

性质1：第i层上至多有2i-1个结点性质2：深度为k的完全二叉树至多有2k - 1个结点性质3： n0, n1, n2分别代表结点度数为0, 1, 2的结点。n为结点总数，N为边的总数，则满足： ①n = n0 + n1 + n2 ②N = n - 1 = n1 + 2n2 ③n0 = n2 + 1性质4：具有n个结点的完全二叉树的深度为└log2n┘+ 1性质5：如果对一颗有n个结点的完全二叉树（其深度为└log2n┘+1）的结点按层序编号，对于任意结点i有： ①如果i = 1，则结点 i 是二叉树的根结点，无双亲；如果i > 1，则其双亲结点是└i/2┘ ②如果2i > n，则节点 i 无左孩子；否则其左孩子就是 2i ③如果2i + 1 > n，则节点i无右孩子；否则其右孩子就是2i + 1 1.2.3 性质推导性质3推导：这个推导印象还是很深的，老师当时上课讲的场景仍历历在目：从边出发即可，用N表示边的总数。树从下往上看，除了根结点，每个结点都由一条边引出：N = n0 + n1 + n2 - 1 树从上往下看，每个结点可以引出0/1/2条边：N = n1 + 2n2 联立可得：n0 = n2 + 1 （“从下往上"和"从上往下"可以分别从"入度”、“出度”）去理解。性质4推导：对于完全二叉树来说：2k-1 - 1 < n swap(h[u], h[t]); down(t); } } void up(int u){ while(u / 2 > 0 && h[u / 2] > h[u]){ swap(h[u / 2], h[u]); u /= 2; } } // 堆的O(n)初始化 for(int i = n / 2; i; i --) down(i);

注：这里有人会疑问，两个操作会不会超时？其实不是，因为就算数据量是106，log(n)即树高也就20。

2.3 堆支持的操作

堆应该支持以下5种操作，其中前3种操作是STL库有的，后2种操作是自己可以实现的。5种操作都可以通过down()和up()函数结合实现。

插入一个数求集合当中最小值删除最小值删除任意一个元素修改任意一个元素

①插入一个数

h[++ size] = x; up(size);

②求集合当中最小值

h[1];

③删除最小值删除最小值这里有个技巧：用整个堆的最后一个元素覆盖掉堆顶元素，然后size - 1，再down()就可以。原因：删除最后一个元素操作简单，只需要size - 1

h[1] = h[size]; size --; down(1);

④删除任意一个元素和删除最小值唯一不同的是，我们不知道用最后一个元素替上去以后应该up还是down，最好的操作就是两个都写上，符合哪个用哪个。

h[k] = h[size]; size --; down(k); up(k);

⑤修改任意一个元素

heap[k] = x; down(k); up(k); 3 堆排序算法（无映射关系）

无映射关系的堆排序是最常见的堆排序，思路是：先把整个数组建成堆，每次输出栈顶即可。堆排序只需要用到上面的两种操作：求集合当中的最小值、删除最小值。（其实就是down()操作了）题目链接：堆排序代码：

#include #include using namespace std; const int N = 100010; int h[N]; // heap int cnt; // 结点总数 void down(int u){ int t = u; // t = u和它两个结点中的最小值 if(u * 2 int n, m; scanf("%d%d", &n, &m); for(int i = 1; i swap(h[a], h[b]); swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]); }

为了凸显3的重要性（懒），这里就不专门列出来其他要改的所有操作了，在代码中会有注释。题目链接：模拟堆代码：

#include #include #include using namespace std; const int N = 100010; int h[N], cnt; int hp[N], ph[N]; void heap_swap(int a, int b){ swap(h[a], h[b]); swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]); } void up(int u){ while(u / 2 && h[u] int t = u; if (u * 2 int n, m = 0; scanf("%d", &n); while(n --){ char op[5]; int k, x; scanf("%s", op); if(!strcmp(op, "I")){ // 插入一个数 scanf("%d", &x); cnt ++; m ++; ph[m] = cnt, hp[cnt] = m; h[cnt] = x; up(cnt); } else if(!strcmp(op, "PM")) printf("%d\n", h[1]); else if(!strcmp(op, "DM")){ // 删除最小值 heap_swap(1, cnt); cnt --; down(1); } else if(!strcmp(op, "D")){ // 删除第k个插入的数 scanf("%d", &k); k = ph[k]; heap_swap(k, cnt); cnt --; up(k); down(k); } else{ // 修改第k个插入的数 scanf("%d%d", &k, &x); k = ph[k]; h[k] = x; up(k); down(k); } } return 0; } 参考资料

[1] 百度百科：满二叉树 [2] 完全二叉树的性质

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章