1、引言
《算法竞赛进阶指南》中指出，在二叉树中，有两组非常重要的条件，分别是两类数据结构的基本性质。
其一是“堆性质”，若二叉树中的任意一个节点的权值都大于等于（小于等于）其父亲节点，则称该二叉树满足“小顶堆性质（大顶堆性质）”。
其二是“BST性质”，二叉树上的每个节点都带有一个数值，称为该节点的键值 $key$，树中的任意一个节点的 $key$ 均同时满足：大于等于其左子树中任意节点的 $key$，小于等于其右子树中任意节点的 $key$。
在日常的刷题过程中，经常会用到优先队列、set、map等STL的容器，但是实际上它们的底层实现某种程度上可以说是二叉堆或者BST，而且二叉堆和BST作为较基础的数据结构，我们应当学会如何实现。
2、二叉堆的实现
struct Heap { int sz; int heap[maxn]; void up(int now) { while(now>1) { int par=now>>1; if(heap[now]<heap[par]) //子节点小于父节点，不满足小顶堆性质 { swap(heap[par],heap[now]); now=par; } else break; } } void push(int x) //插入权值为x的节点 { heap[++sz]=x; up(sz); } inline int top(){return heap[1];} void down(int now) { while((now<<1)<=sz) { int nxt=now<<1; if(nxt+1<=sz && heap[nxt+1]<heap[nxt]) nxt++; //取左右子节点中较小的 if(heap[now]>heap[nxt]) //子节点小于父节点，不满足小顶堆性质 { swap(heap[now],heap[nxt]); now=nxt; } else break; } } void pop() //移除堆顶 { heap[1]=heap[sz--]; down(1); } void del(int p) //删除存储在数组下标为p位置的节点 { heap[p]=heap[sz--]; up(p), down(p); } inline void clr(){sz=0;} };
3、二叉堆的应用
3.1、POJ 1456
3.2、二叉堆优化Dijkstra
3.3、BZOJ 1150
4、二叉搜索树
普通的二叉搜索树每次期望复杂度为 $O(log n)$，但是非常容易退化为 $O(n)$，因此实际应用中一般使用平衡二叉查找树。
4.1、伸展树Splay
伸展树原理：
伸展树实现：
POJ 3580 - SuperMemo - [伸展树splay]
4.2、Treap