参考书籍《挑战程序设计》，本文实质为该书的学习笔记，结合了笔者自己的理解，欢迎指错~
数据结构指的是存储数据的方式。用不同的方式存储数据，可以对数据做不同的高效操作
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
1.树和二叉树
树
树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树
“二叉树”是树中所有节点的儿子个数都不超过2的树
几种二叉树的例子 
2.优先队列和堆
优先队列
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有*先出 （first in, largest out）的行为特征
举例：
某个优先队列能够完成下列操作：
·插入一个数值
·取出最小的数值（获得数值，并且删除）
能够使用堆的二叉树高效地解决上述问题
堆
堆（heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 (ki <= k2i,ki <=k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
堆最重要的性质就是儿子的值一定不小于父亲的值。除此之外，树的节点是按从上到下、从左到右的顺序紧凑排列的。
*在向堆中插入数值时，首先在堆的末尾插入该数值，然后不断向上提升直到没有大小颠倒为止。
*从堆中删除最小值时，首先把堆的最后一个节点的数值复制到根节点上，并删除最后一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中，如果有两个儿子，那么选择数值较小的儿子进行交换（当儿子比自己小时）。
堆的操作的复杂度：堆的两种操作所花的时间都和树的深度成正比。因此，如果一共有n个元素，那么每个操作可以在O（logn）的时间内完成。
堆的实现：
给每个节点编号，并用数组来存储。此时，儿子的编号就满足如下性质：
*左儿子的编号是自己的编号 × 2 + 1
*右儿子的编号是自己的编号 × 2 + 2
代码如下：
int heap[MAX_N], sz = 0;
void push(int x)
{
//自己节点的编号
int i = sz ++;
while(i > 0)
{
//父亲结点的编号
int p = (i - 1) / 2;
//如果已经没有大小颠倒，则退出
if(heap[p] <= x) break;
//把父亲节点的数值放下来，而自己提上去
heap[i] = heap[p];
i = p;
}
heap[i] = x;
}
int pop()
{
//最小值
int ret = heap[0];
//要提到根的数值
int x = heap[--sz];
//从根开始向下交换
int i = 0;
while(i * 2 + 1 < sz)
{
//比较儿子的值
int a = i * 2 + 1, b = i * 2 + 2;
if(b < sz && heap[b] <heap[a]) a = b;
//如果已经没有大小颠倒，则退出
if(heap[a] >= x) break;
//把儿子的数值提上来
heap[i] = heap[a];
i = a;
}
heap[i] = x;
return ret;
}
使用C++标准库实现优先队列：
（不同于上一个例子，这里取出数值时得到的是最大值）
代码如下：
#include <queue>
#include <cstdio>
using namespace std;
int main()
{
priority_queue<int> pque;
pque.push(3);
pque.push(5);
pque.push(1);
while(!pque.empty())
{
printf("%d\n", pque.top());
pque.pop();
}
return 0;
}例题1：Expedition（POJ 2431）
你需要驾驶一辆卡车行驶L（1≤L≤1000000）单位距离。最开始时，卡车上有P（1≤P≤1000000）单位的汽油。卡车每开1单位距离需要消耗1单位的汽油。如果在途中车上的汽油耗尽，卡车就无法继续前行，因而无法到达终点。在途中一共有N（1≤N≤10000）个加油站。第i个加油站在距离起点Ai（1≤Ai≤L）单位距离的地方，最多可以给卡车加Bi（1≤Bi≤100）单位的汽油。假设卡车的燃料箱的容量是无限大的，无论加多少油都没有问题。那么请问卡车是否能到达终点？如果可以，最少需要加多少次汽油？如果可以到达终点，输出最少的加油次数，否则输出-1.
PS：实际上原题的输入数据中给的是加油站到终点的距离，这里为了方便起见，改成了从起点到加油站的距离
输入：
4 （N）
25 （L）
10（P）
10 14 20 21（A）
10 5 2 4（B）
输出：
2（在第一个和第二个加油站加油）
思路：
转换理解方式。在卡车开往终点的途中，只有在加油站才可以加油→在到达加油站i时，就获得了一次在之后的任何时候都可以加Bi单位汽油的权利
即当燃料为0时，再考虑使用之前经过的某个加油站的汽油。
显然，应该选能加油量Bi最大的加油站。
∴可以使用从大到小的顺序依次取出数值的优先队列
在经过加油站i时，往优先队列里加入Bi。
当燃料箱空了时：
如果优先队列也是空的，则无法到达终点
否则取出优先队列中的最大元素，并用来给卡车加油。
代码如下：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int MAX_N = 10000;
int L, P, N;
int A[MAX_N + 1], B[MAX_N + 1];
int main()
{
scanf("%d%d%d", &N, &L, &P);
for(int i = 0; i < N; i++)
scanf("%d", &A[i]);
for(int i = 0; i < N; i++)
scanf("%d", &B[i]);
//为了方便，把终点也认为是加油站
A[N] = L;
B[N] = 0;
N++;
//维护加油站的优先队列
priority_queue<int> que;
int ans = 0;//加油次数
int pos = 0;//现在所在的位置
int tank = P;//油箱中的汽油量
for(int i = 0; i < N; i++)
{
int d = A[i] - pos;//接下来要前进的距离
//不断加油直到油量足够行驶到下一个加油站
while(tank - d < 0)
{
if(que.empty())
{
ans = -1;
break;
}
tank += que.top();
que.pop();
ans++;
}
tank -= d;
pos = A[i];
que.push(B[i]);
}
printf("%d\n", ans);
return 0;
}
例题2：Fence Repair（PKU 3253）
农夫约翰为了修理栅栏，要将一块很长的模板切割成n（1≤n≤20000）块。准备切成的模板的长度为L1、L2、... 、Ln（0≤Li≤50000），未切割前木板的长度恰好为切割后木板长度的总和。例如长度为21的木板要切成长度为5、8、8的三块木板。长21的木板切成13、8的板时，开销是21。再将长度为13的板切成长度为5、8的板时，开销是13。于是合计开销为34。请求出按照目标要求将木板切割完最小的开销是多少。
输入：
3
8 5 8
输出：
34
思路：
公式：木板的长度×节点的深度
（忽略我小学生的字罢0.0）
最短的板与次短的板应当是兄弟节点，且最短的板应当是深度最大的叶子结点之一。由于只需要从板的集合中取出最短的两块，并把长度为两块板长度之和的板加入和（ans）中即可，因此使用优先队列可以高效地实现。
代码如下：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX_N = 20005;
int N, L[MAX_N];
int main()
{
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &L[i]);
ll ans = 0;
//声明一个从小到大取出数值的优先队列
priority_queue<int, vector<int>, greater<int> > que;
for(int i = 0; i < N; i++)
que.push(L[i]);
//循环到只剩一块木板为止
while(que.size() > 1)
{
int l1 = que.top();
que.pop();
int l2 = que.top();
que.pop();
//合并两块木板
ans += l1 + l2;
que.push(l1 + l2);
}
printf("%lld\n", ans);
return 0;
}
3.二叉搜索树
所有的结点，都满足左子树上的所有节点都比自己的小，而右子树上的所有节点都比自己大这一条件。二叉树能够高效地管理数的集合。
二叉搜索树能够高效地完成如下操作：
- 插入一个数值
- 查询是否包含某个数值
- 删除某个数值
插入和查找都比较容易理解，动手画一下就好啦
但删除有些麻烦，因为可能需要移动结点
分以下几种情况处理：
- 需要删除的结点没有左儿子，把右儿子提到需要删除的结点上
- 需要删除的节点的左儿子没有右儿子，把左儿子提到需要删除的结点上
- 以上两种情况都不满足，把左子孙中最大的节结点提到需要删除的结点上
二叉搜索树的复杂度
不论哪一种操作，所花的时间都和树的高度成正比。平均复杂度为O（logn）