前言
   眾所周知，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...  閱讀全文      摘要: 迭代器的分類與框架    迭代器是一種設計模式，用來訪問容器對象的內容而無須暴露容器的內部實現，而多叉樹是一種具有遞歸性質的復合對象，因此它的迭代器是一種復合迭代器，且存在多種遍歷順序和策略，如前序、后序、廣度、葉子、兄弟等，為了支持實現這種復合迭代器，就需要設計不同的迭代器類，由于迭代器封裝了對多叉樹的訪問，而這種訪問又可分為只讀和讀寫兩類，它們在stl中的實現就...  閱讀全文