ACM竞赛所用数据结构1.ppt

二叉堆 一种特殊的树形数据结构，每个结点都有一个值。二叉堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。 建堆 O(n*log(n))/ O(n); 插入元素 log(n); 删除最大/最小元素log(n); 无论是插入还是删除，最关键的都在于调整。 STL heap make_heap(a,a+n,cmp) 默认是最大堆化，即cmp为真时a做叶子 pop_heap(a,a+n,cmp) 将堆顶元素移至a[n-1]且a[0:n-2]仍为堆 push_heap(a,a+n,cmp) 将a[n-1]加入堆a[0:n-2] sort_heap(a,a+n,cmp) 将堆a[n-1]化为排序好的数组a[n-1] bool cmp(int x,int y){ return xy; //最大堆 } a[0]为堆顶元素。 映射2分堆 二项堆不能删除任意元素 在二项堆的基础上，加上一个索引之后，就成了映射2分堆，这时候就可以在log(n)的时间内删除元素。 而Fibonacci堆也支持插入、删除、查找最大最小元素，算法复杂度都很低，但是编程复杂度却很高。 几种堆的比较 优先队列 #includequeue #includevector priority_queue int, vectorint, greaterint q3; Priority_queue struct Rec{ char word[20]; }; struct CMP{ //特别的，重载的是() bool operator () (const Rec a,const Rec b) const{ return strcmp(a.word,b.word)0; } } priority_queueRec,vectorRec,CMP pq; Trie树的插入 Trie树的插入 首先根据插入纪录的关键码找到需要插入的结点位置 如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可 Trie树的删除 Trie树的删除 根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 否则只需要将此分支设置为空即可 后缀树和后缀数组 百度百科中 后缀树 /view/117678.html 后缀数组 /view/1240197.htm 附件中相关资料 后缀树.pdf 后缀数组.doc 关于后缀数组 字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在ACM比赛中中后缀数组比后缀树要更为实用。 树 树的一般表示法 数组父亲表示法 儿子节点表示法（用指针构建多叉树） 比赛的时候常用vector来构造 左儿子右兄弟表示法 哈夫曼树 ? 哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。 定义： 结点之间的路径长度：从一个结点到另一个结点之间的分支数目。 树的路径长度：从树的根到树中每一个结点的路径长度之和。(PL) 哈夫曼树 PL计算 哈夫曼树 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作： WPL为最小的二叉树就称作最优二叉树或哈夫曼树。 哈夫曼树 WPL的计算 完全二叉树不一定是最优二叉树。 哈夫曼树构造算法（贪心） （1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。 哈夫曼树的构造图 树状数组 树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a[1...n]，那么查询a[1] + …… + a[i] 的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。