摘要:    在《基于双端堆实现的优先级队列（1）：原理》一文中讲述了双端堆的相关原理，本文则详细讲述具体的内部实现，便于区分，内部函数名称都以双下划线作为前缀，在这里，有几个关键问题需要说明    1）怎么求一个结点的对称结点：如果完全二叉树根结点从索引1开始但不存储元素，那么最小堆根结点则在索引2，最大堆根结点则在索引3，4和5为2的左右孩...  阅读全文 前言
   众所周知，stl中的优先级队列是基于最大堆实现的，能够在对数时间内插入元素和获取优先级最高的元素，但如果要求在对数时间内还能获取优先级最低的元素，而不只是获取优先级最高的元素，该怎么实现呢？可以用最大堆-最小堆或双端堆数据结构来实现，最大堆-最小堆和双端堆都是支持双端优先队列的插入、删除最小元素和最大元素等操作的堆，在这些操作上，时间复杂度都是对数时间，但是双端堆的操作比最大堆-最小堆的相应操作还要快一个常数因子，而且算法更加简单，因此本文讲述选择使用双端堆实现优先级队列的原理。

定义与性质
   双端堆是一颗完全二叉树，该完全二叉树要么为空，要么满足以下性质：
 （1）根结点不包含元素
 （2）左子树是一个最小堆
 （3）右子树是一个最大堆
 （4）如果右子树不为空，则令i是左子树中任一结点，j是i在右子树中的对应结点，如果i在右子树中的对应结点不存在，则j为i的父结点在右子树中的对应结点，  对于结点i和j，i的关键字值小于等于j的关键字值。
   从以上性质可以推出：对于左子结中的任一结点i，设j为i的对称结点，则由最小元素到i，i到j，j到最大元素的路径上元素是非递减有序的。在双端堆上的操作算法核心就是为了保证这样的单向路径上元素必须是非递减有序的。
   例如下图所示，就是一个双端堆
操作算法
 （1）插入元素：设所插结点为i，其对称结点为j，要分2种情况 a）当i处于最小堆时，则j处于最大堆中，如果KeyValue(i)>KeyValue(j)，则设置value= KeyValue(i)，KeyValue(i)=KeyValue(j)，并执行在最大堆中位置j处插入值value的操作；否则执行在最小堆中位置i处插入值KeyValue(i)的操作。b）当i处于最大堆时，则j处于最小堆中，如果KeyValue(i)<KeyValue(j)，则设置value=KeyValue(i)，KeyValue(i)=KeyVaue(j)，并执行在最小堆中位置i处插入值value的操作；否则执行在最大堆中位置j处插入值KeyValue(i)的操作。

 （2）删除最小元素：首先在最小堆中执行一个向下回溯过程，这个过程执行的堆大小要比原来的堆小1，从最小元素结点开始，每次选取关键字值较小的孩子结点，并用其值更新父结点值，直到底部没有孩子结点，执行的结果是在底部某叶子结点i处形成一个空洞（形象说法，这个空洞需要后续操作来调整填补，下同），i的对称结点j在最大堆中，设最末元素结点为e，如果KeyValue(e)>KeyValue(j)，则设置KeyValue(i)=KeyValue(j)，并执行在最大堆中位置j处插入值KeyValue(e)的操作；否则执行在最小堆中位置i处插入值KeyValue(e)的操作。

 （3）删除最大元素：这个操作比删除最小元素要麻烦一点，和删除最小元素类似，先执行一个向下回溯过程得到空洞结点i，其对称结点为j，为了保证能满足双端堆的性质，需要考虑以下几种情况：a）j只存在一个孩子，如下图第1个所示。 b）j存在两个孩子，如下图第2个所示。 c）j不存在孩子，但存在左兄弟（可能存在孩子），如下图第3个所示。 d）j不存在孩子，但存在右兄弟，如下图最后一个所示。
令min为具有较小值的结点，max为具有较大值的结点，最末元素结点为e，value=KeyValue(e)，如果j存在孩子结点，则 min为孩子中关键字值较小的结点，max为关键字值较大的结点；否则min为j和其兄弟结点中关键字值较小的结点，max为关键字值较大的结点。如果KeyValue(min)<value而且value<KeyValue(max)，在这种情况下，只需调整i或其父结点、max的值即可，操作如下：如果KeyValue(i)<KeyValue(max)，则设置KeyValue(parent(i))=KeyValue(max)，否则设置KeyValue(i)=KeyValue(max)，最后设置KeyValue(max)=value；如果KeyValue(max)<=value，在这种情况下，则执行在最大堆中位置i处插入值value的操作；如果value<=KeyVlaue(min)，在这种情况下，先调整i或其父结点、max的值（见上），再执行在最小堆中位置min处插入值value的操作。

 （4）构造堆：给定一个元素大小为N的序列S，在这个序列空间上构造堆，一般有两种实现方法，一是循环N-1次，每次插入元素S[i]，也就是自顶向下构建堆，时间复杂度为O(NlgN)。另一种是从最后一个内部结点N/2左右开始，执行调整堆操作，直到第一个元素，也就是自底向上构建堆，时间复杂度为O(N)。

 （5）最大堆（最小堆）插入：这是一个向上回溯过程，和单个最大堆（最小堆）操作是一样的，从底部某处开始，比较待插元素和结点关键字值大小，直到前者不大于（不小于）后者时或碰到最大堆（最小堆）顶部为止，这时就找到了插入位置，将待插元素放到这个位置即可。

   设双端堆元素个数为N，由于完全二叉树高度为O(lgN)，则插入元素操作时间复杂度为O(lgN)，删除最小元素和最大元素为不超过2O(lgN)，实现这些操作最重要的一点就是要保证性质4，只有当性质4满足时，双端堆才有意义，才能保证获取最大元素和最小元素操作的对数时间，具体的实现详见下文。      摘要: 类型定义     在多叉树中，深度遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1&n...  阅读全文    一、default constructor---默认构造函数，亦即无参构造函数。从对象构造语义上讲，可分为以下2种：1）trivial 平凡的，可以理解为浅构造  2）notrivial 非平凡的，可以理解为深构造。当一个class没有显式地(explicitly)声明或定义任何constructor的时候，一个default constructor就会被编译器隐式地（implicitly)声明或定义出来。那么这个implicitly default constructor到底是trivial还是notrivial的呢？对于一个class，当存在以下4种情况时，其implicitly default constructor就是notrivial的。
   （1）class内含一个或多个成员对象(member object)，且这些member object中至少一个存在default constructor（无论是显式的default constructor还是隐式的notrival default constructor）
   （2）class派生自一个继承串链，其中至少有一个base class存在default constructor（再次强调，无论是显式的default constructor还是隐式的notrival default constructor）
   （3）class声明一个或多个虚函数(virtual function)
   （4）class派生自一个继承串链，其中至少有一个虚基类(virtual base class)，而不管这些virtual base class是否存在default constructor
   显而易见，这4种情况是正交的，当不存在以上4种情况时，其implicitly default constructor就是trivial的。只有notrivial的default constructor才会被编译器真正生成，而trivial的不会生成。

   二、copy constructor---拷贝构造函数，亦即带有当且仅有一个参数，类型为同类对象的构造函数。从对象拷贝语义上讲，可分为以下2种：1）bitwise copy 位拷贝，可以理解为浅拷贝  2）no bitwise copy 非位拷凡，可以理解为深拷贝。当一个class没有显式地声明或定义copy constructor时，一个copy constructor就会被编译器隐式地声明或定义出来。那么这个implicitly copy constructor到底是bitwise copy还是no bitwise copy的呢？对于一个class，当存在以下4种情况时，其implicitly copy constructor就是no bitwise copy的。
   （1）class内含一个或多个成员对象，且这些member object中至少一个存在copy constructor（无论是显式的copy constructor还是隐式的no bitwise copy constructor）
   （2）class派生自一个继承串链，其中至少有一个base class存在copy constructor（再次强调，无论是显式的copy constructor还是隐式的no bitwise copy constructor）
   （3）class声明一个或多个虚函数
   （4）class派生自一个继承串链，其中至少有一个虚基类，而不管这些virtual base class是否存在copy constructor
   显而易见，这4种情况是正交的，当不存在以上4种情况时，其implicitly copy constructor就是bitwise copy的。只有no bitwise copy的copy constructor才会被编译器真正生成，而bitwise copy的不会生成。

   三、对于defualt constructor，当一个class内显式地存在constructor（包括default constructor）时，编译器不会再生成它，但如果这个class满足以上4种情况至少一种时，编译器就需要负责执行相关的初始化：对于(1)要调用成员对象的default constructor；对于(2)要调用基类的default constructor；对于(3)要设定虚函数表的指针；对于(4)要设定虚基类的指针和偏移量。而这些初始化在用户代码执行前。
        
   四、对于copy constructor，当一个class内显式地存在copy constructor时，编译器不会再生成它，但如果这个class满足以上情况(3)或(和)(4)时，编译器就需要负责执行相关的拷贝：对于(3)要决定怎么设定虚函数表指针。对于(4)要决定怎么设定虚基类的指针和偏移量。同理类推，如果这个class满足情况(1)或(和)(2)，而且其成员对象或基类子对象又满足情况(3)或(和)(4)时，编译器也需要负责执行相关的拷贝了。而这些拷贝在用户代码执行前。      摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1/***************************************************************************************&...  阅读全文      摘要: 类型定义    在多叉树中，叶子遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1  &nb...  阅读全文      摘要: 类型定义    在多叉树中，兄弟遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1   ...  阅读全文 方法1：使用find和xargs命令
     find dir | xargs grep str，dir是指某个目录
     find file | xargs grep str，file是指某个文件
   注意：这种方法，会递归搜索子目录

方法2：直接使用grep命令
     grep str dir/*，dir是指某个目录，但不递归搜索其子目录
     grep -r str dir/*，使用-r选项，递归搜索其子目录
     grep str file，file是指某个文件

方法3：综合以上两种，写一个shell脚本，代码如下 

 1#! /bin/bash
 2# findstr.sh   
 3
 4if [ $# -lt "2" ]; then
 5   echo "Usage: `basename $0` path name [option]"
 6   exit 1
 7fi   
 8
 9path=$1
10name=$2  
11shift 
12shift   
13
14for option in "$@"
15do
16   case $option in
17   -r) dir_op="-r"
18   ;;
19   -i) lu_op="-i"
20   ;;
21   *) if [ -n "$option" ]; then
22         echo "invalid option"
23         exit 1
24       fi
25   ;;
26  esac
27done    
28
29grep_str_of_file()
30{
31     file=$1
32     str=$2
33     out=$(grep -n $lu_op "$str" "$file")
34     if [ -n "$out" -a "$file" != "$0" ]; then
35        echo "$file: $out"
36     fi
37}    
38
39find_str()
40{
41  if [ -d "$1" ]; then
42     for file in $1/*
43      do
44        if [ "$dir_op" = "-r" -a -d "$file" ]; then
45            find_str $file $2
46        elif [ -f "$file" ]; then
47           grep_str_of_file $file $2
48        fi
49     done
50 elif [ -f "$1" ]; then
51   grep_str_of_file $1 $2    
52 fi
53}  
54
55find_str $path $name

  这样一来，不管$1参数是目录还是文件，都能处理，使用示例如下：
    findstr /usr/include main          不递归搜索子目录，大小写敏感
    findstr /usr/include main -i       不递归搜索子目录，忽略大小写
    findstr /usr/include main -r       递归搜索子目录，大小写敏感
    findstr /usr/include main -r  -i   递归搜索子目录，忽略大小写 
    findstr main.cpp main              在文件中搜索，大小写敏感
    findstr main.cpp main -i           在文件中搜索，忽略大小写 

  上面所述的示例中，str不限于特定的文本，可以是带正则表达式的匹配模式。而第3种方法，也可以用sed替换grep来显示文本行，在此基础上能作更多的处理，比如格式化显示、统计匹配的文本个数、搜索策略等，在此就不详究了。      摘要: 类型定义    在多叉树中，后序遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1 &nb...  阅读全文      摘要: 类型定义    在多叉树中，前序遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下： Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1  &n...  阅读全文