2020-09-06

C++ 基础

Cpp 是一种通用编程语言，它扩展了 C 语言，加入了面向对象编程的特性。

数据类型

数据类型
1. 简单类型
  - 基本类型：
    - 整型：int通常是机器的最自然大小，占4B。short：短整数 2B。long：长整数，4 或 8B(取决于编译器和系统)。long long：长长整数，至少64位(8 byte)。INT_MIN = -2147483648 = 1 + INT_MAX
    - 浮点型：float 单精度浮点数 4B；double双精度 8B；long double 8B 或 16B。
    - 字符型：C++ 中表示字符的基本类型char，通常是 1B。字符用 ASCII 编码，以 ASCII 值参与运算
    - 空类型 void
  - 用户定义类型：枚举类型 enum
2. 结构类型：数组 [ ]，结构 struct，联合 union，类 class
3. 指针类型（*）
  
  类型长度（字节）表示范围备注
  
  char 1 -128 ~ 127 -2^7 ~ 2^7-1
  
  int 4 -2147483648 ~ 2147483647 -2^31 ~ 2^31-1
  
  double双精度型 8 -1.710^308 ~ 1.710^308 15位有效数字

类型	长度（字节）	表示范围	备注
char	1	-128 ~ 127	-2^7 ~ 2^7-1
int	4	-2147483648 ~ 2147483647	-2^31 ~ 2^31-1
double双精度型	8	-1.710^308 ~ 1.710^308	15位有效数字

十六进制[hexadecimal]：使用数字 0-9 和字母 A-F（或 a-f）来表示数值，每个十六进制位对应四个二进制位。

1
2

int hexValue = 0x1A3F;        // 0x 表示十六进制，用位运算进行十六进制的操作，输出时显示为二进制
cout << hex << value << endl; // 使用iomanip中的 hex 控制符来设置输出为十六进制格式

ASCII码：是一种将字符映射到数字的编码标准。ASCII码用于表示键盘上的字符，每个字符都对应一个唯一的数字。
0-“\0”(空字符,字符串结束标志)、9-“\t”(制表符：四个空格)、10-“\n”(换行符)、32-“ “(空格)
48-“0”(字符0)、65-“A”、 97-“a” 大小写差32（tolower()大写字符转换为小写）
转义字符 “\ character”：以 “\” 为前缀，表示改变后面 character 符号或整数值的意义，使其成为控制符或字符值。
char16_t：UTF-16字符类型。 char32_t：UTF-32字符类型。char16/32_t 是引入的字符类型，用于支持 Unicode 字符。

类型转换

int a = 65; string b = '9', s = "80";
char c = (char)a;         // ASCII -> char: 65 -> '65' 类型强制转换或显式转换
char d = a + '0';         // int -> char: 65 + '0' -> '65'
int e = b - '0';          // char -> int: '9' - '0' -> 9
int f = stoi(s);          // string -> int
string g = to_string(a);  // int - > string

常量
- 字面常量：字面常量是源代码中的常量值。例如，整数字面常量（ 5、-10）、浮点数字面常量（ 3.14、-0.001）、字符常量（'a'、'B'）、字符串字面常量（"Hello"、"C++"）等。值在程序编译时就已经确定。
- const 关键字创建的常量：在C++中，可以使用 const 关键字创建常量变量。这些变量在声明时被初始化，并且一旦被赋值后就不能再修改其值。例如：const double PI = 3.14159;
- 枚举常量（Enumeration Constants）：使用 enum 关键字定义的枚举类型也可以产生常量。枚举常量是一组具有整数值的符号常量。例如：enum Day { MON, TUE, WED, THU, FRI, SAT, SUN };

数据访问

名访问：程序被编译后，系统对已声明对象保存一张名表，登记对象的属性 < 名字，类型，地址 >

地址访问

double  b  // < b, double, 0X0066FDEC >
&b         // 取对象b的地址	
b          // 访问对象b	
*(&b)      // 间址访问

指针变量：能够存放对象地址的变量。定义形式：类型 * 标识符 ;

1
2
3

int * iptr; // iptr 是指向整型对象的指针，可以存放一个整型变量的地址
char * s ;	  // s 是指向字符对象的指针
int  ** p2;  int  * p1;  int  i = 3;  p1 = & i;  p2 = & p1; // 指向指针的指针

引用：引用说明为对象建立引用名，即别名；
- 引用在定义初始化时与对象名绑定，程序中不能对引用重定义；一个对象的别名，从使用方式和效果上与使用对象名一致
- 定义形式: 类型 & 引用名 = 对象名；
指向常量的指针：间址访问只读。定义形式：const 类型 * 指针或类型 const * 指针
指针常量：指针常量的值只能在定义的时候初始化。定义形式：类型 * const 指针
常引用：const 类型 & 引用名 = 对象名 ;

运算

类型转换：表达式求值之前，要对操作数进行必要的类型转换
1. 将短数扩展为机器处理的长度：参与算术运算的只有5种类型数据
  char、short -> int，unsigned char、unsigned short -> unsigned int，float -> double、long、unsigned long
2. 使运算符两端的操作数具有相同的类型： “向高看齐”，向表达能力强的类型转换；逐个算符转换
运算符的优先关系
- 单目运算符 > 乘除运算 > 加减运算 > 关系运算 > 逻辑与 > 逻辑或 > 赋值 > 逗号
- i + 1 < j * 4 && ! P || Q 等价于 : ( ( ( i +1 ) < ( j * 4 ) ) && ( ! P ) ) || Q
- P != i < j || Q && S 等价于 : ( P != ( i < j ) ) || ( Q && S )
自增、自减
- 前缀式：先增值后引用例：x = ++ i 相当于 i = i + 1 ; x = i ;
- 后缀式：先引用后增值例：x = i ++ 相当于 x = i ; i = i + 1 ;
- 自增、自减算符的运算对象只能是整型变量，不能为常量或表达式

位运算

16进制表示: 0xff -> 1111 1111

int a = 5, b = 3;        // a 二进制: 0101, b 二进制: 0011
int andResult = a & b;   // 0001 (1) 按位与 `&`
int orResult = a | b;    // 0111 (7) 按位或 `|`
int xorResult= a ^ b;    // 0110 (6) 按位异或 `^`
int notA = ~a;           // 1010 (-6 in two's complement representation) 按位取反 `~`
int leftShift = a << 1;  // 1010 (10) 左移<<：将操作数的每个位向左移动指定的位数，右侧用零填充
int rightShift= a >> 1;  // 0010(2) 右移>>：每个位右移指定位数，左侧用符号位(对于有符号数)或零填充

程序控制结构

所有程序都只能包含三种控制结构：顺序结构、选择结构和循环结构
if 语句，while语句，do-while语句，for语句

switch语句：根据一个整型表达式的值决定程序分支

switch(表达式)
{   case 常量表达式 1 : 语句 1  // case 标签是用来匹配 switch 后面表达式的值，执行相应的代码
    …
    case 常量表达式 n : 语句 n
    default : 语句 n+1        // 如果没有任何一个 case 匹配成功，用 default 标签来执行默认的操作
}

表达式类型为非浮点型；各常量表达式类型要与之匹配；各常量表达式要求各不相等；default 子句可选。
缺省时，没有匹配值 switch 语句为空
case 和 default 仅起语句标号作用，不能控制程序流程；一旦选中一个case分支后，将继续往下顺序执行（剩余所有）语句序列。添加 break 语句可以跳出 switch 语句体，达到控制流程作用

函数

库函数：预定义的函数，它们提供了各种功能，可以通过包含相应的头文件来使用。
C++标准库是一个包含许多有用函数和类的集合，可以使用这些函数和类来构建程序，而不必从头开始编写所有功能。
iostream 是一个C++标准库的头文件，提供了输入输出操作，包括 cin 和 cout。
cmath 是另一个头文件，提供了数学函数如指数函数pow(10.0, 2)、平方根sqrt()、三角cos()、绝对值abs() 等。
algorithm 中含有sort()、reverse()、swap()等函数。
string 是一个代表字符串string的类，它封装了许多处理字符串的函数和操作符。如substr()、find()函数等。
vector vec.size()获取 vector 的大小

命名空间：是用于组织代码标识符（如变量、函数、类等）的一种方式，以避免命名冲突。命名空间允许你在不同的命名空间中定义相同名称的标识符，从而使不同部分的代码可以使用相同的名字而不会产生冲突。C++标准库中的函数和类通常被放置在一个叫做 std 的命名空间中。你可以使用命名空间限定符 std:: 来访问其中的成员。

1
2

#include <iostream>     // 这是一个预处理指令，用于包含C++标准库中的 `iostream` 头文件。这个头文件包含了用于输入输出的流对象（如 `cin` 和 `cout`）以及其他相关函数。
using namespace std;    // 这是一个命名空间声明。`std` 是C++标准库的命名空间，包含了许多标准函数、对象和类。通过使用 `using namespace std;`，你可以在代码中直接使用 `cout` 和 `endl`，而无需在前面加上 `std::` 前缀。注意，虽然使用 using namespace std; 可以简化代码，但在大型项目中，为了避免命名冲突，可能会选择显式地使用命名空间限定符。

函数定义形式：类型函数名（形式参数表） { 语句序列 }
函数调用形式：函数名（实际参数表）
函数原型：作用是告诉编译器有关函数的信息：函数的名字、函数返回的数据类型、函数要接受的参数个数、参数类型和参数的顺序；编译器根据函数原型检查函数调用的正确性。函数原型的形式：类型函数名（形式参数表）;
函数参数的传递：值传递，指针传递，引用传递
传值参数：调用函数时，实参表达式的值被复制到相应形参标识的对象中，并按形参类型强制转换；函数内对形参的访问、修改，都在形参的标识对象进行；函数返回时，形参对象被撤消，不影响实参的值；值传送的实参可以是常量、有确定值的变量或表达式；函数返回值通过匿名对象传递

丨函数 FunctionObj 丨数据 DataObj 丨数组 DataObj

地址丨FunctionObj、&FunctionObj、FunctionObj、&FunctionObj 丨&DataObj 丨第i行第j列元素：a[i]+j、*(a+i)+j、&a[i][j]
函数、应用程序是编译器处理的对象，每一个函数模块都有一个首地址，称为函数的入口地址。
函数调用：找到函数入口地址；传递参数。函数入口地址：就是不带括号的函数名。
函数指针：指向函数的指针变量，值为函数的入口地址。函数的类型是函数的接口，可以通过指针变量的间址方式调用函数
- 若有函数类型为：double ( double, double ) ; 或 typedef double functionType ( double, double ) ;
- 定义指向这类函数的指针变量：double ( * fp ) ( double, double ); 或 functionType * fp1 , * fp2 ;

	丨函数 FunctionObj	丨数据 DataObj	丨数组 DataObj
地址	丨FunctionObj、&FunctionObj、FunctionObj、&FunctionObj	丨&DataObj	丨第i行第j列元素：a[i]+j、*(a+i)+j、&a[i][j]

结构

结构由数目固定的成员构成，各成员可以具有不同的数据类型，一个结构变量在内存占有一片连续的存储空间

结构类型定义形式为：

struct  标识符
{  类型   成员1 ;
   …
   类型   成员n ;
};

可以用不同方法定义一个结构变量：(1) 声明类型之后声明变量 (2)声明类型的同时声明变量 (3)直接声明结构类型变量
访问结构变量的成员：（1）结构变量.成员（2）结构指针 -> 成员， (*结构指针 ) . 成员

STL

C++的STL（Standard Template Library，标准模板库）是C++标准库的一部分，它提供了一组通用的模板类和函数，用于实现常见的数据结构和算法。STL的设计目标是提供高效、通用、可复用的组件，以帮助开发者编写更加优雅和高效的C++代码。

容器（Containers）：容器是用于存储和管理一组对象的类模板。STL提供多种容器，每个容器都有不同的特性和适用场景。
vector：动态数组，支持快速的随机访问，底层实现是array，封装后使用更友好。list：双向链表，支持在任意位置插入和删除元素。deque：双端队列，类似于动态数组。map：关联数组，使用键值对存储数据。set：集合，存储不重复的值。

vector<int> dp(cost.size() + 1);               // 指定数据类型、数组大小
vector<vector<int>> dp(3, vector<int>(4));     // 创建一个包含3行4列的二维 vector
vector<int> vec = {1, 2, 3};  
sort(vec.begin(), vec.end());                  // 利用迭代器排序
vec.push_back(4);  vec.pop_back();             // 添加数据、移除末尾元素

算法（Algorithms）：STL提供了一组强大的通用算法，这些算法可以用于各种容器类型。这些算法涵盖了排序、查找、遍历、变换等多种操作。一些常见的算法包括： sort：对容器中的元素进行排序。find：在容器中查找特定元素。for_each：对容器中的每个元素执行操作。transform：将容器中的元素进行转换操作。
迭代器（Iterators）：迭代器用于遍历容器中的元素，提供了统一的访问接口，使得代码更具可扩展性。迭代器分为多种类型，包括输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。(begin()、end()、++、–、* 、== 和 !=)
函数对象（Function Objects）：函数对象是类的实例，可以像函数一样被调用。STL的算法和其他组件允许你使用函数对象来执行操作，或者使用标准库提供的一些预定义的函数对象。
适配器（Adapters）：适配器是用于转换或扩展容器或迭代器接口的类模板。例如，std::stack 是一个基于双端队列的堆栈容器适配器，std::queue 是一个基于双端队列的队列容器适配器。

输入输出

通常通过标准库中的 iostream 完成，包括 cin 用于从用户获取数据， cout 向屏幕输出数据，endl 输出一个换行符。
格式化输出：用到 iomanip 库
setw 和 setfill：这两个函数可以用来设置输出的宽度和填充字符。
1
cout << setw(6) << setfill('0') << 42; // 将数字 42 输出为 "000042"，总宽度为 6，使用 '0' 填充
fixed + setprecision：用于输出指定小数位数的浮点数。
1
cout << fixed << setprecision(2) << 3.1415926;

如果要处理多行输入可以使用 getline 函数，需要包含 iostream 头文件

#include <sstream>
string input; 
int number;
getline(cin, input);         // 读取整行输入：1 -1 -1 0
istringstream ss(input);     // 使用 istringstream 来分割数字
while (ss >> number) {```}   // 逐个获取数字

数据结构与算法

时间复杂度

时间复杂度是一种用来衡量算法运行时间与输入规模之间关系的概念。它不是用来精确测量程序运行时间的，而是描述在输入规模变化时，算法运行时间的增长趋势。
大O表示上界，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

数组

数组（Array）是有序的元素序列。数组是一种固定大小的数据结构，用于存储相同类型的元素。在C++中，数组的长度在创建时就固定了，无法在运行时改变。数组的元素是连续存储在内存中的，可以通过索引访问。数组有一些限制，例如长度固定、不能动态扩展等。当数组作为函数参数传递时，实际上传递的是指向数组首元素的指针。
1
int myArray[5]; int numbers[3] = {10, 20, 30}; int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 声明并初始化一个整数数组
在C++中，动态声明数组意味着在运行时根据需要分配数组的内存空间，而不是在编译时固定数组大小。
使用指针声明数组： 首先，你需要声明一个指针变量，该指针变量将用于存储动态分配的数组的地址。然后，使用内存分配函数（如 new 或 malloc）分配所需大小的内存空间。
释放内存： 在不再需要数组时，必须手动释放分配的内存，以避免内存泄漏。使用 delete 或 free 来释放内存。
1
int* dynamicArray = new int[size]; delete[] dynamicArray; // 动态分配数组内存释放分配的内存
数组容器（Array Container）：在C++中，数组（Array）和数组容器（Array Container）是两种不同的数据结构，它们在用法和特性上有一些区别。数组容器是C++标准库中提供的一种数据结构，用于存储相同类型的元素，并提供了一些更方便的功能。
array 是一个数组容器，它在内部使用数组来存储元素，是一个类模板，具有类似对象的行为，可以使用成员函数和操作符进行操作，提供了更多的功能，如获取数组大小、迭代器、操作符重载等，还可以像其他C++容器一样与STL算法一起使用。
1
#include <array> array<int, 5> myArray; array<int, 3> numbers = {10, 20, 30}; // 声明一个包含3个整数的array

动态数组vector的底层实现是 array，严格来讲vector是容器，不是数组。

#include <vector>
vector<int> myVector = {1, 2, 3, 4, 5};   // vector<int> myVector(n)  大小为n的空vector
// vector<vector<int>> myMatrix(n, vector<int>(n, 0))  n阶二维vector
myVector.push_back(1);    // 或直接下标索引 myVector[0] = 1;
for (const int& value : myVector)  cout << value;  // for (int i=0;i<myVector.size();i++){..}
for (vector<int>::iterator it = myVector.begin(); it != myVector.end(); ++it)  cout << *it;
myVector.pop_back();
if (myVector.empty())  cout << myVector.size();

sort函数接受两个迭代器参数，即要排序的范围的开始和结束位置。排序默认是升序的，如果需要降序排序，可以使用 std::greater
() 作为第三个参数。在使用 sort 函数之前，请确保引入了
头文件。
1
2
sort(arr, arr + n);
sort(data.begin(), data.end(), greater<int>());

链表

处理头结点有两种方式：直接使用原来的链表来进行删除操作、设置一个虚拟头结点在进行删除操作。
使用 ListNode* cur = head 进行链表操作，不要直接使用头结点操作！！！
判断空指针为 if(ptr != nullptr) ，不要用 if(!ptr)
nullptr与NULL：NULL 是一个宏定义，通常被定义为整数 0，NULL 用于表示空指针存在一些问题，因为它实际上是一个整数，可能会导致类型不匹配和模糊的代码。nullptr 是 C++11 标准引入的新关键字，用于表示空指针，是类型安全的，可以隐式转换为任何指针类型，但不会导致模糊的类型问题。推荐在现代 C++ 代码中使用 nullptr 来表示空指针。
1
2
ListNode* head = new ListNode(5); // 初始化节点
delete head; // 删除节点，回收内存

哈希表

在C++中，哈希（Hash）是一种将数据映射到固定大小的散列值的技术。哈希函数将输入数据转换为散列值，这个散列值通常用于快速查找或存储数据。C++标准库提供了一些哈希函数和相关的数据结构，让你可以在自己的程序中应用哈希。

什么时候使用哈希法？当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

哈希容器（Hash Containers）：C++标准库提供了一些哈希容器，它们使用哈希函数来快速存储和检索数据。
unordered_set：基于哈希表的集合，用于实现无序映射。类似于 set，但具有更快的查找性能。set 是一个有序的容器，它存储一组唯一的元素。
unordered_map：基于哈希表的关联数组，不保持元素的插入顺序，类似于 map但具有更快的查找性能。map 是一个有序（按键的字典顺序）的键-值对容器，它存储一组唯一的键，并且每个键关联一个值。

unordered_map<Key, T> mapp;                 // 创建一个空的无序映射。
mapp[x]                                     // 直接访问指定键的值，如果键不存在，会创建一个新的键并初始化为默认值。
insert({key, value})   erase(key)           // 插入，删除一个键值对。
at(key)                                     // 访问指定键的值，如果键不存在会抛出异常。
find(key)                                   // 查找指定键，返回指向该键的迭代器，若不存在，返回mapp.end() 
empty()   size()                            // 检查是否为空；返回键值对的数量
begin()   end()                             // 返回迭代器，用于遍历所有键值对。
for (const auto& pair : mapp) {             // 范围循环,遍历所有键值对。
    cout << pair.first << pair.second;
}    
                                            // set的用法类似

字符串

访问 string 字符串特定索引位置的字符时，返回的类型是 char

直接使用 + 连接字符串和字符串string/字符char；
使用 ==、!=、<、<=、>、>= 比较字符串和字符串string/字符char；
使用cstring库中的字符串处理函数。其中，strcmp() 用于比较两个 C 风格字符串，strcpy()复制。

getline(cin, str)                            // cin以空格分隔string。而getline()会等待用户在终端输入一行字符串，然后将该字符串存储在 str 变量中。注意，getline() 会读取一行完整的输入，包括换行符，并且将换行符从输入中删除。
str.append(count, '0')                       // 在str末尾加上count个'0'
str.substr(i, 8)                             // 从位置i开始截取长度为8的str的子串
str.erase(i, 5);                             // 从位置i开始，删除5个字符
str1.compare(str2)                           // 逐字符比较字符串(字典顺序)大小，返回0/1/-1
reverse(s.begin() + 0, s.begin() + n);       // algorithm库字符串翻转函数，翻转范围[0, n-1]
void reverse(string& s,int start,int end){   // 自制字符串反转函数，reverse(str, 0, str.size()-1)
    for (int i = start, j = end; i < j; i++, j--)  swap(s[i], s[j]);    
}

栈与队列

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈、队列的底层结构。
不允许有遍历行为，不提供迭代器。
所以STL 栈、队列不被归类为容器，而被归类为container adapter（容器适配器）。

栈（Stack）遵循后进先出（Last-In-First-Out，LIFO）的原则。 std::stack 容器用于实现栈。

#include <stack>
stack<int> myStack;               // 创建一个空的栈，存储整数
myStack.push(10);                 // 添加元素到栈
myStack.top();                    // 访问栈顶元素
myStack.pop();                    // 移除栈顶元素
while (!myStack.empty()) {...     // 遍历栈

队列（Queue）遵循先进先出（First-In-First-Out，FIFO）的原则。 std::queue 容器用于实现队列。

1 2	#include <queue> queue<int> myQueue; myQueue.push(10); myQueue.front(); myQueue.pop(); while (!myQueue.empty()) {...

`list`（双向链表）

std::list 是一个双向链表容器，每个元素都包含一个指向前一个元素和一个指向后一个元素的指针。这使得插入和删除操作在链表中非常高效，但随机访问较慢。以下是一些 std::list 的常见用法：

#include <list>
    std::list<int> myList;
    myList.push_back(1);                                 // 插入元素
    myList.push_front(2);          
    myList.insert(std::next(myList.begin()), 3);         // 在迭代器位置后插入
    myList.pop_back();                                   // 删除元素
    myList.pop_front();
    myList.erase(std::next(myList.begin()));             // 删除迭代器位置的元素
    for (const int& item : myList) { cout << item,,      // 遍历元素

`deque`（双端队列）

deque 是双端队列容器，支持在两端进行高效的插入和删除操作，并且允许随机访问。它的特性使得它在需要在两端进行频繁操作的场景下很有用。以下是一些 deque 的常见用法：

#include <deque>
std::deque<int> myDeque;
myDeque.push_back(1);                                   // 插入元素
myDeque.push_front(2);  
myDeque.pop_back();                                     // 删除元素
myDeque.pop_front();
myDeque.push_back(3);                                   // 随机访问
myDeque.push_back(4);
int value = myDeque[1];                                 // 访问第二个元素，值为4
for (const int& item : myDeque) { cout << item ;;;      // 遍历元素
}

`Heap`（堆）

在 C++ 中，你可以使用 priority_queue 来实现小顶堆和大顶堆。默认情况下，priority_queue 是大顶堆，但你可以通过改变比较函数来实现小顶堆或大顶堆。

实现大顶堆：

#include <queue>
// 创建一个大顶堆（默认情况）
priority_queue<int> maxHeap;
// 向大顶堆中插入元素
maxHeap.push(5);    maxHeap.push(2);    maxHeap.push(8);    maxHeap.push(1);
// 访问堆顶元素（最大值）
cout << "最大值：" << maxHeap.top() << std::endl;
// 弹出堆顶元素
maxHeap.pop(); ；；}

实现小顶堆：

#include <queue>
// 创建一个小顶堆
// 第一个参数 int：这是容器中存储的元素的类型，也就是小顶堆中的元素类型。在这里，我们使用 int 类型。
// 第二个参数 vector<int>：这是容器类型，用于存储小顶堆的元素。通常情况下，我们使用 std::vector 作为容器，但你也可以使用其他容器类型，比如 std::deque。
// 第三个参数 greater<int>：这是比较函数对象，用于定义小顶堆的比较规则。在这里，greater<int> 是一个函数对象，它表示比较时采用递增的方式，即根节点的值小于子节点的值。
priority_queue<int, vector<int>, greater<int>> minHeap;
// 向小顶堆中插入元素
minHeap.push(5);  minHeap.push(2);  minHeap.push(8);  minHeap.push(1);
// 访问堆顶元素（最小值）
cout << "最小值：" << minHeap.top() << std::endl;
// 弹出堆顶元素
minHeap.pop();；；}

二叉树

二叉树（Binary Tree）是一种常见的树状数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。每个节点都存储一个值，这个值可以是任何类型，取决于树的应用。
1
2
3
4
5
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则为满二叉树。
完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
二叉搜索树 BST：具有有序性质，适用于快速查找、插入和删除操作。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉搜索树 AVL： 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn。
而unordered_map、unordered_set底层实现是哈希表。