标签： 数据结构

• 堆的建立有两种方式，一个向上调整，一个向下调整，这两个得到的结果可能不同
  • 向上调整一般用于边输入数据边建立，是给定数字顺序插入
  • 向下调整一般是将所有结点先加入到一棵完全二叉树中，然后对二叉树的所有非叶子结点进行向下调整（从非叶子结点n/2开始，一直到1）
    

向上调整（大顶堆为例）：

向下调整（以大顶堆为例）：先将所有输入得到的数组存储到heap[i]中（构成了一颗完全二叉树，下标从1开始）

 

【数据结构】堆、堆排序笔记

• 堆是一棵完全二叉树，树的每个结点的值都不小于（或者不大于）其左右孩子的值。
• 父亲结点大于等于孩子结点的值叫做大顶堆，反之叫做小顶堆
• 大顶堆的每个结点的值都是以它为根结点的子树的最大值，反之最小值
• 下面都以大顶堆为例子：
• 两个兄弟之间不存在大小比较关系，堆只能说明某结点引导的子树的所有子结点都比它小，就像领导关系一样，下属之间或者领导之间可能有实力高低，但是领导是他的所有下属的最高级
• 建堆：把所有非叶子结点都向下调整（从n/2开始直到1）
• void createHeap() { for(int i = n / 2; i >= 1; i--) downAdjust(i, n); }

  1 2 3 4

  void createHeap() {   for(int i = n / 2; i >= 1; i--)     downAdjust(i, n); }

• 向下调整：（不断和自己的左右孩子比较，把孩子的最大值和自己交换，直到结点的下标大于最后一个元素的数组下标high为止。记住：i结点的左孩子j结点满足j = i * 2;）

• const int maxn = 100; int heap[maxn], n = 10; //对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标 void downAdjust(int low, int high) { int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子 while(j <= high) { if(j + 1 <= high && heap[j + 1] > heap[j]) j = j + 1; //那就让j存储数值最大的那个结点所对应的下标 if(heap[j] > heap[i]) { swap(heap[i], heap[j]); i = j; j = i * 2; } else { break; } } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  const int maxn = 100; int heap[maxn], n = 10;   //对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标 void downAdjust(int low, int high) {   int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子   while(j <= high) {     if(j + 1 <= high && heap[j + 1] > heap[j])       j = j + 1; //那就让j存储数值最大的那个结点所对应的下标     if(heap[j] > heap[i]) {       swap(heap[i], heap[j]);       i = j; j = i * 2;     } else {       break;     }   } }

• 删除堆顶元素（用最后一个元素覆盖堆顶元素，然后让n- -，然后向下调整）
• void deleteTop() { heap[1] = heap[n--]; downAdjust(1, n); }

  1 2 3 4

  void deleteTop() {   heap[1] = heap[n--];   downAdjust(1, n); }

• 增加一个元素（添加到最后一个结点的后面，然后进行向上调整操作）
• void insert(int x) { heap[++n] = x; upAdjust(1, n); }

  1 2 3 4

  void insert(int x) {   heap[++n] = x;   upAdjust(1, n); }

• 向上调整操作就是把将要调整的结点与父亲结点比较，如果权值比父亲结点大，那么就交换其与父亲结点，这样反复比较，直到到达堆顶或者是父亲结点的权值比较大为止
• void upAdjust(int low, int high) {//low一般传入1，high为将要调整的结点的数组下标 int i = high, j = i / 2; //i为将要调整结点，j为其父亲 while(j >= low) { if(heap[j] < heap[i]) { swap(heap[j], heap[i]); i = j; j = i / 2; } else { break; } } }

  1 2 3 4 5 6 7 8 9 10 11

  void upAdjust(int low, int high) {//low一般传入1，high为将要调整的结点的数组下标   int i = high, j = i / 2; //i为将要调整结点，j为其父亲   while(j >= low) {     if(heap[j] < heap[i]) {       swap(heap[j], heap[i]);       i = j; j = i / 2;     } else {       break;     }   } }

• 堆排序：
  • 在建堆完毕后，堆排序就是取出堆顶元素，然后将堆的最后一个元素i替换至堆顶，再进行一次针对堆顶元素1向下调整(1, i – 1)范围，直到堆中只有一个元素为止（i == 2）
• void heapSort() { createHeap(); for(int i = n; i >= 2; i--) { swap(heap[i], hea[1]); downAdjust(1, i - 1); } }

  1 2 3 4 5 6 7

  void heapSort() {   createHeap();   for(int i = n; i >= 2; i--) {     swap(heap[i], hea[1]);     downAdjust(1, i - 1);   } }

树状数组（Binary Indexed Tree, BIT）

• 本质上是按照二分对数组进行分组，维护和查询都是O(lgn)的复杂度
• 树状数组与线段树：树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。

• lowbit
  • lowbit = x & (-x)
  • lowbit(x)也可以理解为能整除x的最大的2的幂次

• c[i]存放的是在i号之前（包括i号）lowbit(i)个整数的和（即：c[i]的覆盖长度是lowbit(i) ）
• 树状数组的下标必须从1开始

单点更新，区间查询

int getsum(int x)函数：返回前x个整数之和

• 如果要求[x, y]之内的数的和，可以转换成getsum(y) – getsum(x – 1)来解决

void update(x, v)函数：将第x个数加上一个数v

经典应用：统计序列中在元素左边比该元素小的元素个数

如果是求序列第k大的问题：

可以用二分法查询第一个满足getsum(i) >= k的i

如果给定一个二维整数矩阵A，求A[1][1]~A[x][y]这个子矩阵中所有元素之和，以及给单点A[x][y]加上整数v：

只需把getsum和update函数中的for循环改为两重

区间更新，单点查询

• 将getsum改为沿着i增大lowbit(i)的方向
• 将update改为沿着i减小的lowbit(i)的方向
• c[i]不再表示这段区间的元素之和，而是表示这段区间每个数被加了多少
• int getsum(int x)返回第x个整数的值（就是从小块到大块累加一共被增加了多少）

• void update(int x, int v)是将前x个整数都加上v

---

• 所以，~~i从x往后是从小块更新到大块c[i]，i从x往前是累加前面的覆盖块的值~

1057. Stack (30)-PAT甲级真题（树状数组）

• 求栈内所有元素的中位数：用排序查询的方法会超时~~~用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快~

并查集（Union、Find、Set）支持两个操作：合并两个集合、查找：判断两个元素是否在一个集合。

用一个与n等长的数组存储每个结点的父结点：

初始化，先令它们属于各自不同的集合，父结点都是自己：

查找：不断找父结点直到father[x] = x，递推或者递归方法都可以

合并两个集合：找到a和b的根结点，如果根结点不同，就把其中一个的最高处的根结点的父亲设为另一个根结点

*对findFather函数进行路径压缩：

• 按原先的写法（递推写法）先获得根结点root
• 重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点root

• 如果判定条件是两个人有共同喜欢的课程，可以开一个数组course[1000]，1000为课程数，course[t]表示任意一个喜欢t课程的人的编号，这样的话，如果course[t] == 0说明当前读入的这个课程就他自己一个人喜欢，那么就令course[t] = i，他自己就是喜欢课程t的人的编号。findFather(course[t])就是这个人所在的社交网络的根结点，只需要合并当前读入的人的编号i和findFather(course[t])，表示把这两个人合并到了同一个圈子。

• 如果要统计一共有多少个圈子，只需要遍历一遍1~n，把它们的父结点对应的isRoot数组++，那么isRoot[i] = j表示以i为父结点的社交圈子中有j个人~~~

• 如果两个人之间不是可传递的关系，可以用一个二维数组enemy[a][b] = enemy[b][a] = 1存储a和b之间是否有关系。

已知后序与中序输出前序（先序）：
后序：3, 4, 2, 6, 5, 1（左右根）
中序：3, 2, 4, 1, 6, 5（左根右）
分析：因为后序的最后一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打印右子树。左子树在后序中的根结点为root – (end – i + 1)，即为当前根结点-(右子树的个数+1)。左子树在中序中的起始点start为start，末尾end点为i – 1.右子树的根结点为当前根结点的前一个结点root – 1，右子树的起始点start为i+1，末尾end点为end。
输出的前序应该为：1, 2, 3, 4, 5, 6（根左右）

已知前序（先序）与中序输出后序：
前序：1, 2, 3, 4, 5, 6（根左右）
中序：3, 2, 4, 1, 6, 5（左根右）
分析：因为前序（根左右）最先出现的总是根结点，所以令root为前序中当前的根结点下标（并且同时把一棵树分为左子树和右子树）。start为当前需要打印的子树在中序中的最左边的下标，end为当前需要打印的子树在中序中最右边的下标。递归打印这棵树的后序，递归出口为start > end。i为root所表示的值在中序中的下标，所以i即是分隔中序中对应root结点的左子树和右子树的下标。
先打印左子树，后打印右子树，最后输出当前根结点pre[root]的值。
输出的后序应该为：3, 4, 2, 6, 5, 1（左右根）