逸人の博客

积累 C++ 性能优化的操作和思路

杂记

二叉搜索树与二叉平衡树

堆的定义 是完全二叉树：只允许最后一行不为满，且最后一行必须从左往右排序，最后一行元素之间不可以有间隔。特性适合数组存储。 层序遍历给节点编号，元素存入数组对应下标，下标节点为 i ，其子节点则为 2i+1 2i+2 。 堆的基本操作上滤（上浮） / 下滤（下沉） 下滤根节点向下调整 若（根）节点元素小于其最大子节点，则交换，直至该元素所在节点大于其所有子节点或移动到底部（无子节点），形成大根堆。 复杂度为 O(logN) 。自下而上建堆，从倒数第二行父节点开始向下调整，复杂度为 O(N) 。 上滤子节点向上调整 与父节点比较，大于父节点则交换，直到无法上移。 主要用于插入新元素到堆尾，复杂度为 O(logN) 。自顶向下建堆，每次插入到堆尾后向上调整，复杂度为 O(NlogN) 。 堆的应用优先队列 priority_queue默认为最大堆弹出堆顶元素后，堆尾元素移至根节点，重新进行上滤或下滤操作直至有序。 堆排序就是把优先队列元素依次弹出，为降低空间复杂度，实际排序时堆顶弹出的元素与堆尾元素交换并存放，最终形成的树做层序遍历便是有序...

值类别参考 lvalue: 左值，可取地址，如变量名。 prvalue: 纯右值，如 int(42) 临时量。 xvalue: 将亡值， 如表达式 std::move(obj)。 纯右值和将亡值都统称右值（rvalue），可以是不具名的临时变量，可以是即将离开作用域或被 move 的类型。左值和将亡值都属于泛左值。 Attention值类别（value category）只看“表达式的静态属性”，跟对象本身的状态无关。变量本身没有值类别，只有表达式才有。 12int x = 42;decltype(auto) b = std::move(x); 当以后写 b 这个标识符时，它所在的表达式是左值（因为具名变量都是左值表达式），但它的声明类型仍然是 int&&。 std::move()Attentionstd::move 只是“告诉编译器这个表达式可以当右值用”；对象是否、何时、如何被掏空，取决于随后真正被调用的移动操作。 std::move 无条件把表达式强制转换为右值引用类型的 xvalue 表达式（类型是 int&&，类别是 xvalu...