树、堆是用于频繁插入、排序的数据结构。他是一种排序数据结构而不是排序算法。
堆和树是有区别的
书上给的例子有点奇怪:
他的意思是说:“删除最小+添加一个新数+再找最小”这种操作时间复杂度高,所以需要用堆。我在想:你如果先对列表进行一次排序,然后再进行“删除最小+添加一个新数+再找最小”,不就省事了(取第一个,挨个比较插入,再取第一个)?但是发现这比较评价得比较 N/2 次,但是如果用堆的话就只要比较 logN 就好。也就是说有这个好处
好处:假如你想要招生招到全省前100名,你至少得把所有人的成绩都看一遍,不然万一你漏了一个同学,而那个同学恰好更强怎么办?这个数据结构能够说:假如你想要招生招到全省前100名,我不用看所有人的成绩了,我看几个就可以知道了,不用担心漏掉的人能有更高的分数。
我本来以为有个什么数的数据结构(类似 queue、stack的),但其实用列表就好(因为完全二叉树是有索引规律的,完全可以依据索引来找到父、子)!当然这个列表是经过排序的,但不是从小到大排序,是建立一个父节点一定比子节点小的完全二叉树,然后把数上的数值按顺序放入列表里面。
我一开始不清楚这个向上、向下移动用在哪个情况下,不都是插入吗?是不是如果数中缺了数,破坏了结构,就向下移动,如果不缺,就向上移动。目前只能这样理解了。
// 堆的建立与排序
#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<int>& 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<int> &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<int> num_list{ 99,5,36,7,22,17,92,12,2,19,25,28,1,46 }; int t = 0;
// 从一般开始往前面判断 7-1
for (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;
}