树、堆是用于频繁插入、排序的数据结构。他是一种排序数据结构而不是排序算法。

堆和树是有区别的

• 堆：特殊的完全二叉树。“特殊”：数值上特殊，父比子大/小。

1. 为什么用它

书上给的例子有点奇怪：

他的意思是说：“删除最小+添加一个新数+再找最小”这种操作时间复杂度高，所以需要用堆。我在想：你如果先对列表进行一次排序，然后再进行“删除最小+添加一个新数+再找最小”，不就省事了（取第一个，挨个比较插入，再取第一个）？但是发现这比较评价得比较 N/2 次，但是如果用堆的话就只要比较 logN 就好。也就是说有这个好处

好处：假如你想要招生招到全省前100名，你至少得把所有人的成绩都看一遍，不然万一你漏了一个同学，而那个同学恰好更强怎么办？这个数据结构能够说：假如你想要招生招到全省前100名，我不用看所有人的成绩了，我看几个就可以知道了，不用担心漏掉的人能有更高的分数。

• 这似乎是一个不完全的排序，其实没有给所有人进行排序，但如果我知道你们学校最高分才200名，那这个学校所有的学生都可以排除。
• 比如如果我想知道学校谁最富有，我不需要知道每个同学有多少钱，我只要比每个同学的爸爸有钱就好。
• 有点“本店全市最强、本店全国最强、本店全街最强”的感觉。

2. 如何用？

2.1 建立堆

我本来以为有个什么数的数据结构（类似 queue、stack的），但其实用列表就好（因为完全二叉树是有索引规律的，完全可以依据索引来找到父、子）！当然这个列表是经过排序的，但不是从小到大排序，是建立一个父节点一定比子节点小的完全二叉树，然后把数上的数值按顺序放入列表里面。

2.2 向上、向下移动

我一开始不清楚这个向上、向下移动用在哪个情况下，不都是插入吗？是不是如果数中缺了数，破坏了结构，就向下移动，如果不缺，就向上移动。目前只能这样理解了。

3.3 建立

1. 先随机拍个序号
2. 向下移动（因为树的结构未成形）。从n/2 - > 1号节点进行向下移动。最底层节点不形成树，先不遍历。
3. ？为什么只在一条分支上面往下检查？
   答：因为交换之前，子书是符合规范的，但交换过后，有且仅有一个子树会被破坏，所以不存在既往左边，又向右边。
4. 这里需要注意，不可先和左边比较，然后和右边比较。这会导致你改了左边又改右边，复杂度增加。

// 堆的建立与排序
#include
#include
using namespace std;int find_min(int a, int b, int c = 99) {// 把最小的放第一个 []TODO:有无更好的方法if (a > b) {a = b;}if (a > c) {a = c;}return a;
}void change_pos(vector& num_list, int human_i) {// 如果int note_index = human_i - 1;int child_left = human_i * 2 -1 ;int child_right = human_i * 2;// 父节点是否比所有子节点都小int flag = 0; // 是否影响子节点int exchang_index = note_index;int t = 0;// 如果没有子节点就退出if (human_i > num_list.size() / 2)return;// 这里需要注意，不可先和左边比较，然后和右边比较。这会导致你改了左边又改右边，复杂度增加// 应该三个数取最小:左边先比较，右边后。总共分2类：有右、无右；if (child_right <= num_list.size() - 1) {//有右t = find_min(num_list[note_index], num_list[child_left], num_list[child_right]);if (t == num_list[child_left]) exchang_index = child_left;if (t==num_list[child_right]) exchang_index = child_right;if (exchang_index != note_index) {t = num_list[note_index];num_list[note_index] = num_list[exchang_index];num_list[exchang_index] = t;change_pos(num_list, exchang_index +1);// 转为人的序列}}else {// 无右t = find_min(num_list[note_index], num_list[child_left]);if (t == num_list[child_left]) exchang_index = child_left;//if (t == num_list[child_right]) exchang_index = child_right;if (exchang_index != note_index) {t = num_list[note_index];num_list[note_index] = num_list[exchang_index];num_list[exchang_index] = t;change_pos(num_list, exchang_index + 1);// 转为人的序列}}
}int delete_min(vector &num_list, int i) {// 弹出第一个 没必要删除头：修改头部，去掉最后一个就好int t = 0;t = num_list.front();num_list[0] = num_list.back(); //? back 返回引用会不会有问题？毕竟最后一个是要被删除的num_list.pop_back();change_pos(num_list,1);return t;
}int main() {vector num_list{ 99,5,36,7,22,17,92,12,2,19,25,28,1,46 }; int t = 0;// 从一般开始往前面判断 7-1for (int i = 7; i >= 1; i--) {change_pos(num_list, i);}for (int i = 0; i < 14; i++) {t = delete_min(num_list, i);cout << t << " ";}return 0;
}