1、二叉搜索樹是二叉樹的一種，樹的每個結(jié)點含有一個數(shù)據(jù)項，每個數(shù)據(jù)項有一個鍵值。結(jié)點的存儲位置是由鍵值的大小決定的，所以二叉搜索樹是關(guān)聯(lián)式容器。
(1)、 若它的左子樹不空，則左子樹上所有結(jié)點的鍵值均小于它的根結(jié)點的鍵值；
(2)、若它的右子樹不空，則右子樹上所有結(jié)點的鍵值均大于它的根結(jié)點的鍵值；
(3)、它的左、右子樹也分別為二叉排序樹。
注意：：：二叉排序樹是一種動態(tài)樹表，樹的結(jié)構(gòu)通常不是一次生成的。而是在查找的過程中，當樹中不存在關(guān)鍵字等于給定值的節(jié)點時再進行插入。新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。

2、插入與查找算法：
查找：
（1）、若二叉排序樹非空，將給定值與根節(jié)點的關(guān)鍵字值比較，若相等，則查找成功；
（2）、若不等，則當根節(jié)點的關(guān)鍵字值大于給定值時，到根的左子樹中進行查找；
（3）、否則到根的右子樹中進行查找。若找到，則查找過程是走了一條從樹根到所找到節(jié)點的路徑；
（4）、否則，查找過程終止于一棵空樹。
//① 、普通查找，查找不成功返回NULL
遞歸思想：
 BiTree SearchBST (BiTree *T，KeyType key)
{
    //在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素
    //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，否則返回空指針
        if( (!T)||(key==T—>data.key))
            return (T)； //查找結(jié)束,此時T為NULL，或者為該結(jié)點
        else if (key< T—>data.key)
                return(SearchBST(T—>lchild，key))； //在左子樹中繼續(xù)查找
                else
                return(SearchBST(T —>rchild，key))；// 在右子樹中繼續(xù)查找
    }//SearchBST

非遞歸思想：
BiTree SearchBST (BiTree *root，KeyType key)
{ 
   BiTree *p；
   if( root ＝＝ NULL)return NULL；//查找結(jié)束,此時根為NULL，
   p ＝ root；
   while(p!=NULL)
   { 
        if(p －>key==Key)breat；
       if( Key < p ->key) p ＝p －>lchild；//在左子樹中繼續(xù)查找
         else p ＝ p －>rchild；//在右子樹中繼續(xù)查找
    }
   return p；
}
//② 、查找不成功，返回插入位置
    //在根指針T所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，
    //若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點，并返回TRUE，
    //否則指針p指向查找路徑上訪問的最后一個結(jié)點并返回FALSE，
    //指針f指向T的雙親，其初始調(diào)用值為NULL
 BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)
{
        if(!T) {p=f；return FALSE；} //查找不成功
        else if (key==T—>data.key) 
            {p=T；return TRUE；} //查找成功
           else if (key<T—>data.key) SearchBST(T—>lchild，key，T，p)； //在左子樹中繼續(xù)查找
                        else SearchBST(T—>rchild，key，T，p)；//在右子樹中繼續(xù)查找
    }//SearchBST

插入：
（1）、首先執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點。沒找到則新建子結(jié)點

（2）、判斷被插結(jié)點是其父親結(jié)點的左、右兒子。將被插結(jié)點作為葉子結(jié)點插入。

（3）、若二叉樹為空。則首先單獨生成根結(jié)點

基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的插入算法
相當于新建子樹。
 //當二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時,插入e并返回TRUE，否則返回FALSE
Status Insert BST(BiTree &T，ElemType e)
{
            if(!SearchBST(T，e.key，NULL，p) ) //返回P為插入的結(jié)點點
        { //先查找，不成功新建結(jié)點
            s=(BiTree)malloc(sizeof(BiTNode))；
            s->data=e； s->lchild= s->rchild=NULL；
            if (!p) T = s； //被插結(jié)點*s為新的根結(jié)點 ，原樹為空
            else if (e.key<p->data.key) p->lchild=s； //被插結(jié)點*s為左孩子
                    else p—>rchild=s //被插結(jié)點*s為右孩子
            return TRUE；
          }
        else 
      return FALSE; //樹中已有關(guān)鍵字相同的結(jié)點，不再插入
    }// Insert BST

  void InsertBST(BSTree *Tptr，KeyType key)
      {
//若二叉排序樹 *Tptr中沒有關(guān)鍵字為key，則插入，否則直接返回
        BSTNode *f，*p=*TPtr； //p的初值指向根結(jié)點
        while(p){ //查找插入位置
          if(p->key==key) return；//樹中已有key，無須插入
          f=p； //f保存當前查找的結(jié)點
          p=(key<p->key)?p->lchild：p->rchild；
            //若key<p->key，則在左子樹中查找，否則在右子樹中查找
         } //endwhile
         //f為插入的結(jié)點
        p=(BSTNode *)malloc(sizeof(BSTNode))；
        p->key=key； p->lchild=p->rchild=NULL； //生成新結(jié)點
        if(*TPtr==NULL) //原樹為空
           *Tptr=p； //新插入的結(jié)點為新的根
        else //原樹非空時將新結(jié)點關(guān)p作為關(guān)f的左孩子或右孩子插入
          if(key<f->key)
            f->lchild=p；
          else f->rchild=p；
       } //InsertBST

4、刪除算法
①刪除操作的一般步驟
(1) 進行查找
    　查找時，令p指向當前訪問到的結(jié)點，parent指向其雙親(其初值為NULL)。若樹中找不到被刪結(jié)點則返回，否則被刪結(jié)點是*p。
(2) 刪去*p。
    　刪*p時，應(yīng)將*p的子樹(若有)仍連接在樹上且保持BST性質(zhì)不變。按*p的孩子數(shù)目分三種情況進行處理。

②刪除*p結(jié)點的三種情況
(1)*p是葉子(即它的孩子數(shù)為0)
    　無須連接*p的子樹，只需將*p的雙親*parent中指向*p的指針域置空即可。

(2)*p只有一個孩子*child
    　只需將*child和*p的雙親直接連接后，即可刪去*p。
  注意：
    　*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4種狀態(tài)。
(3)*p有兩個孩子
    　先令q=p，將被刪結(jié)點的地址保存在q中；然后找*q的中序后繼*p，并在查找過程中仍用parent記住*p的雙親位置。*q的中序后繼*p一定是*q的右子樹中最左下的結(jié)點，它無左子樹。因此，可以將刪去*q的操作轉(zhuǎn)換為刪去的*p的操作，即在釋放結(jié)點*p之前將其數(shù)據(jù)復(fù)制到*q中，就相當于刪去了*q。
③二叉排序樹刪除算法
分析：
    　上述三種情況都能統(tǒng)一到情況(2)，算法中只需針對情況(2)處理即可。
    　注意邊界條件：若parent為空，被刪結(jié)點*p是根，故刪去*p后，應(yīng)將child置為根。


算法：刪除關(guān)鍵字為key的結(jié)點
void DelBSTNode(BSTree *Tptr，KeyType key)
 {
//在二叉排序樹*Tptr中刪去關(guān)鍵字為key的結(jié)點
  BSTNode *parent=NUll，*p=*Tptr，*q，*child；
  while(p)
{ 
     //從根開始查找關(guān)鍵字為key的待刪結(jié)點
    if(p->key==key) break；//已找到，跳出查找循環(huán)
    parent=p； //parent指向*p的雙親
    p=(key<p->key)?p->lchild：p->rchild； //在關(guān)p的左或右子樹中繼續(xù)找
 } 
//注意：也可以使用基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的查找算法
//結(jié)果是  parent 記錄了要刪除結(jié)點的父結(jié)點，p指向要刪除的結(jié)點

      if(!p) return； //找不到被刪結(jié)點則返回
     q=p； //q記住被刪結(jié)點*p
     if(q->lchild && q->rchild) //*q的兩個孩子均非空，故找*q的中序后繼*p
    for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
  //現(xiàn)在情況(3)已被轉(zhuǎn)換為情況(2)，而情況(1)相當于是情況(2)中child=NULL的狀況
    child=(p->lchild)?p->lchild：p->rchild；//若是情況(2)，則child非空；否則child為空
    if(!parent) //*p的雙親為空，說明*p為根，刪*p后應(yīng)修改根指針
      *Tptr=child； //若是情況(1)，則刪去*p后，樹為空；否則child變?yōu)楦?br />    else{ //*p不是根，將*p的孩子和*p的雙親進行連接，*p從樹上被摘下
      if(p==parent->lchild) //*p是雙親的左孩子
        parent->lchild=child； //*child作為*parent的左孩子
      else parent->rchild=child； //*child作為 parent的右孩子
      if(p!=q) //是情況(3)，需將*p的數(shù)據(jù)復(fù)制到*q
        q->key=p->key； //若還有其它數(shù)據(jù)域亦需復(fù)制
     } //endif
    free(p)； /釋放*p占用的空間
  } //DelBSTNode
給出三種情況的不同算法
第一種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹;
        while(r->rchild != NULL)//搜索左子樹的最右邊的葉子結(jié)點r
        {
            r = r->rchild;
        }
            r->rchild = p->rchild;
            btree *q = p->lchild;   //q指向其左子樹;
            free(p);
            return q;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子樹;
            free(p);
            return q;
      }
}
第二種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹;
            btree *prer = p->lchild;   //prer指向其左子樹;
        while(r->rchild != NULL)//搜索左子樹的最右邊的葉子結(jié)點r
        {
                  prer = r;
            r = r->rchild;
        }

        if(prer != r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
        {
                  prer->rchild = r->lchild;
                  r->lchild = p->lchild; //被刪結(jié)點p的左子樹作為r的左子樹
            }
        r->rchild = p->rchild; //被刪結(jié)點p的右子樹作為r的右子樹

            free(p);
            return r;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子樹;
            free(p);
            return q;
      }
}

哈夫曼樹定義為：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權(quán)值？什么是路徑長度？什么是帶權(quán)路徑長度呢？
權(quán)值：哈夫曼樹的權(quán)值是自己定義的，他的物理意義表示數(shù)據(jù)出現(xiàn)的次數(shù)、頻率。可以用樹的每個結(jié)點數(shù)據(jù)域data存放一個特定的數(shù)表示它的值。

路徑長度：在一棵樹中，從一個結(jié)點往下可以達到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。

結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。  樹中所有葉子節(jié)點的帶權(quán)路徑長度之和，WPL=sigma(w*l)

2、哈夫曼樹的構(gòu)造過程。（結(jié)合圖例）
假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。 n個權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

　　(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；

　　(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；

　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

　　(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹

3、哈夫曼樹的應(yīng)用：哈夫曼編碼（前綴編碼）
哈夫曼編碼

在數(shù)據(jù)通信中，通常需要把要傳送的文字轉(zhuǎn)換為由二進制字符0和1組成的二進制串，這個過程被稱之為編碼(Encoding)。例如，假設(shè)要傳送的電文為DCBBADD，電文中只有A、B、C、D四種字符，若這四個字符采用表(a)所示的編碼方案，則電文的代碼為11100101001111，代碼總長度為14。若采用表(b) 所示的編碼方案，則電文的代碼為0110101011100，代碼總長度為13。

字符集的不同編碼方案

哈夫曼樹可用于構(gòu)造總長度最短的編碼方案。具體構(gòu)造方法如下：
設(shè)需要編碼的字符集為{d1,d2,…,dn}，各個字符在電文中出現(xiàn)的次數(shù)或頻率集合為{w1,w2,…,wn}。以d1,d2,…,dn作為葉子結(jié)點，以w1,w2,…,wn作為相應(yīng)葉子結(jié)點的權(quán)值來構(gòu)造一棵哈夫曼樹。規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到葉子結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點對應(yīng)字符的編碼就是哈夫曼編碼(Huffman Encoding)。

在建立不等長編碼中，必須使任何一個字符的編碼都不是另一個編碼的前綴，這樣才能保證譯碼的唯一性。例如，若字符A的編碼是00，字符B的編碼是001，那么字符A的編碼就成了字符B的編碼的后綴。這樣，對于代碼串001001，在譯碼時就無法判定是將前兩位碼00譯成字符A還是將前三位碼001譯成B。這樣的編碼被稱之為具有二義性的編碼，二義性編碼是不唯一的。而在哈夫曼樹中，每個字符結(jié)點都是葉子結(jié)點，它們不可能在根結(jié)點到其它字符結(jié)點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。

下圖就是電文DCBBADD的哈夫曼樹：

4、哈夫曼樹的實現(xiàn)

由哈夫曼樹的構(gòu)造算法可知，用一個數(shù)組存放原來的n個葉子結(jié)點和構(gòu)造過程中臨時生成的結(jié)點，數(shù)組的大小為2n-1。所以，哈夫曼樹類HuffmanTree中有兩個成員字段：data數(shù)組用于存放結(jié)點，leafNum表示哈夫曼樹葉子結(jié)點的數(shù)目。結(jié)點有四個域，一個域weight，用于存放該結(jié)點的權(quán)值；一個域lChild，用于存放該結(jié)點的左孩子結(jié)點在數(shù)組中的序號；一個域rChild，用于存放該結(jié)點的右孩子結(jié)點在數(shù)組中的序號；一個域parent，用于判定該結(jié)點是否已加入哈夫曼樹中。

哈夫曼樹結(jié)點的結(jié)構(gòu)為：| 數(shù)據(jù) | weight | lChild | rChild | parent |

     public class Node
    {
        char c; //存儲的數(shù)據(jù)，為一個字符
        private double weight; //結(jié)點權(quán)值
        private int lChild; //左孩子結(jié)點
        private int rChild; //右孩子結(jié)點
        private int parent; //父結(jié)點
        //結(jié)點權(quán)值屬性
        public double Weight
        {
            get
            {
                return weight;
            }
            set
            {
                weight = value;
            }
        }
        //左孩子結(jié)點屬性
        public int LChild
        {
            get
            {
                return lChild;
            }
            set
            {
                lChild = value;
            }
        }
        //右孩子結(jié)點屬性
        public int RChild
        {
            get
            {
                return rChild;
            }
            set
            {
                rChild = value;
            }
        }
        //父結(jié)點屬性
        public int Parent
        {
            get
            {
                return parent;
            }
            set
            {
                parent = value;
            }
        }
        //構(gòu)造器
        public Node()
        {
            weight = 0;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }
        //構(gòu)造器
        public Node(double weitht)
        {
            this.weight = weitht;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }

        //構(gòu)造器
        public Node(int w, int lc, int rc, int p)
        {
            weight = w;
            lChild = lc;
            rChild = rc;
            parent = p;
        }
    }

    public class HuffmanTree
    {
        private Node[] data; //結(jié)點數(shù)組
        private int leafNum; //葉子結(jié)點數(shù)目
        //索引器
        public Node this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //葉子結(jié)點數(shù)目屬性
        public int LeafNum
        {
            get
            {
                return leafNum;
            }
            set
            {
                leafNum = value;
            }
        }
        //構(gòu)造器
        public HuffmanTree(int n)
        {
            data = new Node[2 * n - 1];
            leafNum = n;
        }
        //創(chuàng)建哈夫曼樹
        public void Create(Node[] datain)
        {
            double minL, minR;
            minL = minR = double.MaxValue;
            int lchild, rchild;
            lchild = rchild = -1;

            int length = data.Length;
            //初始化哈夫曼樹
            for (int i = 0; i < length; i++)
                data[i] = new Node();
            for (int i = 0; i < datain.Length; i++)
                data[i] = datain[i];

            //處理n個葉子結(jié)點，建立哈夫曼樹
            for (int i = leafNum; i < length; i++)
            {
                //在全部結(jié)點中找權(quán)值最小的兩個結(jié)點
                for (int j = 0; j < i; j++)
                {
                    if (data[j].Parent == -1)
                    {
                        if (data[j].Weight < minL)
                        {
                            minR = minL;
                            minL = data[j].Weight;
                            rchild = lchild;
                            lchild = j;
                        }
                        else if (data[j].Weight < minR)
                        {
                            minR = data[j].Weight;
                            rchild = j;
                        }
                    }
                }
                data[lchild].Parent = data[rchild].Parent = i;
                data[i].Weight = minL + minR;
                data[i].LChild = lchild;
                data[i].RChild = rchild;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            HuffmanTree tree = new HuffmanTree(5);
            Node[] nodes = new Node[] { new Node(1), new Node(2), new Node(2.5d), new Node(3), new Node(2.6d) };
            tree.Create(nodes);

            Console.ReadLine();
        }
    }

/////////////////////////////節(jié)選自網(wǎng)絡(luò)上的資料、

優(yōu)先隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素。每個元素都有一個優(yōu)先權(quán)或值
/////用堆實現(xiàn)優(yōu)先隊列
1、把優(yōu)先隊列中的元素按優(yōu)先級大小組織成堆，堆頂元素具有最大優(yōu)先級。
2、優(yōu)先隊列的插入與刪除可以用堆的插入與刪除實現(xiàn)。
3、優(yōu)先隊列在定義為priority_queue ，在STL中#include<queue> 中實現(xiàn)、
 priority_queue<int, vector<int>, greater<int> >qi2;

其中
第二個參數(shù)為容器類型。
第三個參數(shù)為比較函數(shù)。

估計還要問問：什么是堆，什么是堆排序？堆與計算機分配內(nèi)存的堆相同嗎？
很多資料給出：堆的定義是
（1）、n個關(guān)鍵字序列（Kl，K2，…，Kn）稱為(Heap)，當且僅當該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))：
ki≤K2i且ki≤K2i+1 或  Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相當于二叉樹的非葉結(jié)點，K2i則是左孩子，k2i+1是右孩子 

（2）若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹： 　　樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。

（3）、根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為小根堆，又稱最小堆。根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆，又稱最大堆。

（4）、堆中任一子樹亦是堆。
（5）、堆可以視為一棵完全的二叉樹，完全二叉樹的一個“優(yōu)秀”的性質(zhì)是，除了最底層之外，每一層都是滿的，這使得堆可以利用數(shù)組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結(jié)點對應(yīng)數(shù)組中的一個元素。

那么堆排序呢？
堆排序其實就是將一組無序的序列變成堆的過程、下面我們一起看看堆排序的算法。
2、堆排序
以最大堆為例，步驟為：
　　① 先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū) 　　② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key 　　③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 　　…… 　　直到無序區(qū)只有一個元素為止。  
將一個無序的序列建成堆的過程實際上是一個反復(fù)篩選的過程。若將此序列看作是一棵完全二叉樹，則最后一個非終端結(jié)點是[n/2](不大于n/2的整數(shù)），因此篩選過程只需從[n/2]開始。要建成一個大頂堆，即先選擇一個值最大的元素并與序列中的最后一個元素交換，然后對序列前n-1元素進行篩選，從新調(diào)整為一個大頂堆，直到結(jié)束。 
算法描述如下： 
  
typedef   int[]   Elem;//采用順序存儲表示完全二叉樹 

void   HeapAdjust(Elem   &e,int   s,int   m) 
{//e中s...m的元素除e[s]之外已經(jīng)滿足堆的定義（e[i] <=e[2*i]&&e[i] <=e[2*i+1] 
  //或e[i]> =e[2*i]&&e[i]> =e[2*i+1]),調(diào)整e[s]使的e[s...m]成為一個大頂堆。 
      selem=e[s]; 
      for(i=2*s;i <=m;i*=2)//沿著值較大的元素（結(jié)點）向下篩選 
      { 
            if(i <m   &&   e[i] <e[i+1])++i;//i為值較大的元素下標 
            if(selem> =e[i])break; 
            e[s]=e[i]; 
            s=i; 
        } 
      e[s]=selem; 
} 

void   HeapSort(Elem   &e) 
{//對順序表排序 
    for(i=e.length/2;i> 0;--i) 
            HeapAdjust(e,i,e.length); 
    for(i=e.length;i> 1;--i) 
    { 
          temp=e[1];                     //將堆中的最后一個元素與第一個元素交換 
          e[1]=e[i]; 
          e[i]=temp; 
          HeapAdjust(H,1,i-1);//調(diào)整1..i-1的元素成為大頂堆 
      }     
}


/////////////////////////////////////////////////////////////
使用堆排序注意的問題：：：
1、序列是從1開始的。，注意定義，R[1..n]，故要空出R[0]。
2、堆排序算法分為兩部分：建立大頂堆和排序。
3、排序的最壞時間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。
4、由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 5、　堆排序是就地排序，輔助空間為O(1)， 它是不穩(wěn)定的排序方法。

問題：當序列空間為R[0,1....n]；時，該怎么去使用堆排序呢？元素后移一位，這明顯不是一個好方法。

數(shù)據(jù)對齊，是指數(shù)據(jù)所在的內(nèi)存地址必須是該數(shù)據(jù)長度的整數(shù)倍。比如DWORD數(shù)據(jù)的內(nèi)存其實地址能被4除盡，WORD數(shù)據(jù)的內(nèi)存地址能被2除盡。x86 CPU能直接訪問對齊的數(shù)據(jù)，當它試圖訪問一個未對齊的數(shù)據(jù)時，會在內(nèi)部進行一系列的調(diào)整，這些調(diào)整對于程序來說是透明的，但是會降低運行速度，所以編譯器在編譯程序時會盡量保持數(shù)據(jù)對齊。

C/C++編譯器在內(nèi)存分配時也保持了數(shù)據(jù)對齊，請看下例：

struct{

short a1;

short a2;

short a3;

}A;

struct{

long  a1;

short a2;

}B;

cout<<sizeof(A)<<","<<sizeof(B)<<endl;//其它代碼略去

結(jié)構(gòu)體A和B的大小分別是多少呢？

默認情況下，為了方便對結(jié)構(gòu)體元素的訪問和管理，當結(jié)構(gòu)體內(nèi)的元素都小于處理器長度的時候，便以結(jié)構(gòu)體里面最長的數(shù)據(jù)為對齊單位，也就是說，結(jié)構(gòu)體的長度一定是最長數(shù)據(jù)長度的整數(shù)倍。

如果結(jié)構(gòu)體內(nèi)部存在長度大于處理器位數(shù)時就以處理器位數(shù)為對齊單位。

結(jié)構(gòu)體內(nèi)類型相同的連續(xù)元素將存在連續(xù)的空間內(nèi)，和數(shù)組一樣。

上例中:

A有3個short類型變量，各自占2字節(jié)，總和為6，6是2的倍數(shù)，所以sizeof(A)=6;

B有一個long類型變量，占4字節(jié)，一個short類型的變量，占2字節(jié)，總和6不是最大長度4的倍數(shù)，所以要補空字節(jié)以增至8實現(xiàn)對齊，所以sizeof(8)=8。

 

在C++類的設(shè)計中遵循同樣的道理，但需注意，空類需要占1個字節(jié)，靜態(tài)變量(static)由于在棧中分配，不在sizeof計算范圍內(nèi)。

多態(tài)性，這個面向?qū)ο缶幊填I(lǐng)域的核心概念，本身的內(nèi)容博大精深，要以一文說清楚實在是不太可能。加之作者本人也還在不斷學(xué)習(xí)中，水平有限。因此本文只能描一下多態(tài)的輪廓，使讀者能夠了解個大概。如果有描的不準的地方，歡迎指出，或與作者探討（作者Email：nicrosoft@sunistudio.com） 
        
        首先，什么是多態(tài)（Polymorphisn）？按字面的意思就是“多種形狀”。我手頭的書上沒有找到一個多態(tài)的理論性的概念的描述。暫且引用一下Charlie   Calverts的對多態(tài)的描述吧——多態(tài)性是允許你將父對象設(shè)置成為和一個或更多的他的子對象相等的技術(shù)，賦值之后，父對象就可以根據(jù)當前賦值給它的子對象的特性以不同的方式運作（摘自“Delphi4   編程技術(shù)內(nèi)幕”）。簡單的說，就是一句話：允許將子類類型的指針賦值給父類類型的指針。多態(tài)性在Object   Pascal和C++中都是通過虛函數(shù)（Virtual   Function）實現(xiàn)的。 
        
        好，接著是“虛函數(shù)”（或者是“虛方法”）。虛函數(shù)就是允許被其子類重新定義的成員函數(shù)。而子類重新定義父類虛函數(shù)的做法，稱為“覆蓋”（override），或者稱為“重寫”。 

        這里有一個初學(xué)者經(jīng)常混淆的概念。覆蓋（override）和重載（overload）。上面說了，覆蓋是指子類重新定義父類的虛函數(shù)的做法。而重載，是指允許存在多個同名函數(shù)，而這些函數(shù)的參數(shù)表不同（或許參數(shù)個數(shù)不同，或許參數(shù)類型不同，或許兩者都不同）。其實，重載的概念并不屬于“面向?qū)ο缶幊?#8221;，重載的實現(xiàn)是：編譯器根據(jù)函數(shù)不同的參數(shù)表，對同名函數(shù)的名稱做修飾，然后這些同名函數(shù)就成了不同的函數(shù)（至少對于編譯器來說是這樣的）。如，有兩個同名函數(shù)：function   func(p:integer):integer;和function   func(p:string):integer;。那么編譯器做過修飾后的函數(shù)名稱可能是這樣的：int_func、str_func。對于這兩個函數(shù)的調(diào)用，在編譯器間就已經(jīng)確定了，是靜態(tài)的（記住：是靜態(tài)）。也就是說，它們的地址在編譯期就綁定了（早綁定），因此，重載和多態(tài)無關(guān)！真正和多態(tài)相關(guān)的是“覆蓋”。當子類重新定義了父類的虛函數(shù)后，父類指針根據(jù)賦給它的不同的子類指針，動態(tài)（記住：是動態(tài)！）的調(diào)用屬于子類的該函數(shù)，這樣的函數(shù)調(diào)用在編譯期間是無法確定的（調(diào)用的子類的虛函數(shù)的地址無法給出）。因此，這樣的函數(shù)地址是在運行期綁定的（晚邦定）。結(jié)論就是：重載只是一種語言特性，與多態(tài)無關(guān)，與面向?qū)ο笠矡o關(guān)！ 
        
        引用一句Bruce   Eckel的話：“不要犯傻，如果它不是晚邦定，它就不是多態(tài)。” 
        
        那么，多態(tài)的作用是什么呢？我們知道，封裝可以隱藏實現(xiàn)細節(jié)，使得代碼模塊化；繼承可以擴展已存在的代碼模塊（類）；它們的目的都是為了——代碼重用。而多態(tài)則是為了實現(xiàn)另一個目的——接口重用！而且現(xiàn)實往往是，要有效重用代碼很難，而真正最具有價值的重用是接口重用，因為“接口是公司最有價值的資源。設(shè)計接口比用一堆類來實現(xiàn)這個接口更費時間。而且接口需要耗費更昂貴的人力的時間。” 
        
        其實，繼承的為重用代碼而存在的理由已經(jīng)越來越薄弱，因為“組合”可以很好的取代繼承的擴展現(xiàn)有代碼的功能，而且“組合”的表現(xiàn)更好（至少可以防止“類爆炸”）。因此筆者個人認為，繼承的存在很大程度上是作為“多態(tài)”的基礎(chǔ)而非擴展現(xiàn)有代碼的方式了。 
        
        什么是接口重用？我們舉一個簡單的例子，假設(shè)我們有一個描述飛機的基類（Object   Pascal語言描述，下同）： 
        type 
                plane   =   class 
                public 
                        procedure   fly();   virtual;   abstract;   //起飛純虛函數(shù) 
                        procedure   land();   virtual;   abstract;   //著陸純虛函數(shù) 
                        function   modal()   :   string;   virtual;   abstract;   //查尋型號純虛函數(shù) 
                end; 
        
        然后，我們從plane派生出兩個子類，直升機（copter）和噴氣式飛機（jet）： 
                copter   =   class(plane) 
                private 
                        fModal   :   String; 
                public 
                        constructor   Create(); 
                        destructor   Destroy();   override; 
                        procedure   fly();   override; 
                        procedure   land();   override; 
                        function   modal()   :   string;   override; 
                end; 
        
                jet   =   class(plane) 
                private 
                        fModal   :   String; 
                public 
                        constructor   Create(); 
                        destructor   Destroy();   override; 
                        procedure   fly();   override; 
                        procedure   land();   override; 
                        function   modal()   :   string;   override; 
                end; 
        
        現(xiàn)在，我們要完成一個飛機控制系統(tǒng)，有一個全局的函數(shù)   plane_fly，它負責(zé)讓傳遞給它的飛機起飛，那么，只需要這樣： 
        procedure   plane_fly(const   pplane   :   plane); 
        begin 
                pplane.fly(); 
        end; 
        就可以讓所有傳給它的飛機（plane的子類對象）正常起飛！不管是直升機還是噴氣機，甚至是現(xiàn)在還不存在的，以后會增加的飛碟。因為，每個子類都已經(jīng)定義了自己的起飛方式。 
        
        可以看到   plane_fly函數(shù)接受參數(shù)的是   plane類對象引用，而實際傳遞給它的都是   plane的子類對象，現(xiàn)在回想一下開頭所描述的“多態(tài)”：多態(tài)性是允許你將父對象設(shè)置成為和一個或更多的他的子對象相等的技術(shù)，賦值之后，父對象就可以根據(jù)當前賦值給它的子對象的特性以不同的方式運作。 
        
        很顯然，parent   =   child;   就是多態(tài)的實質(zhì)！因為直升機“是一種”飛機，噴氣機也“是一種”飛機，因此，所有對飛機的操作，都可以對它們操作，此時，飛機類就作為一種接口。 
        
        多態(tài)的本質(zhì)就是將子類類型的指針賦值給父類類型的指針（在OP中是引用），只要這樣的賦值發(fā)生了，多態(tài)也就產(chǎn)生了，因為實行了“向上映射”。






多態(tài)性

　　是允許將父對象設(shè)置成為和一個或多個它的子對象相等的技術(shù)，比如Parent:=Child； 多態(tài)性使得能夠利用同一類(基類)類型的指針來引用不同類的對象,以及根據(jù)所引用對象的不同,以不同的方式執(zhí)行相同的操作.

c++中多態(tài)更容易理解的概念為

　　允許父類指針或名稱來引用子類對象，或?qū)ο蠓椒ǎ鴮嶋H調(diào)用的方法為對象的類類型方法。
作用　　
把不同的子類對象都當作父類來看，可以屏蔽不同子類對象之間的差異，寫出通用的代碼，做出通用的編程，以適應(yīng)需求的不斷變化。

　　賦值之后，父對象就可以根據(jù)當前賦值給它的子對象的特性以不同的方式運作。也就是說，父親的行為像兒子，而不是兒子的行為像父親。

　　舉個例子：從一個基類中派生，響應(yīng)一個虛命令，產(chǎn)生不同的結(jié)果。

　　比如從某個基類繼承出多個對象，其基類有一個虛方法Tdoit，然后其子類也有這個方法，但行為不同，然后這些子對象中的任何一個可以賦給其基類的對象，這樣其基類的對象就可以執(zhí)行不同的操作了。實際上你是在通過其基類來訪問其子對象的，你要做的就是一個賦值操作。

　　使用繼承性的結(jié)果就是可以創(chuàng)建一個類的家族，在認識這個類的家族時，就是把導(dǎo)出類的對象當作基類的對象，這種認識又叫作upcasting。這樣認識的重要性在于：我們可以只針對基類寫出一段程序，但它可以適應(yīng)于這個類的家族，因為編譯器會自動就找出合適的對象來執(zhí)行操作。這種現(xiàn)象又稱為多態(tài)性。而實現(xiàn)多態(tài)性的手段又叫稱動態(tài)綁定(dynamic binding)。

　　簡單的說，建立一個父類的對象，它的內(nèi)容可以是這個父類的，也可以是它的子類的,當子類擁有和父類同樣的函數(shù)，當使用這個對象調(diào)用這個函數(shù)的時候，定義這個對象的類（也就是父類）里的同名函數(shù)將被調(diào)用，當在父類里的這個函數(shù)前加virtual關(guān)鍵字，那么子類的同名函數(shù)將被調(diào)用。

//轉(zhuǎn)自網(wǎng)友博客、
1、 派生類對象與普通類對象的相同之處在于，可以直接訪問該類的所有對象（包括this指針指向的對象和其他對象）的protected和private成員（包括其基類成員）。不同之處在于派生類對象只能訪問其對應(yīng)基類對象的protected成員（有隱式this指針傳遞），而不能訪問其基類的其他對象的protect成員，而普通類對象則也可以直接訪問該類所有對象的成員。

 

2、 在C++中，基類指針只能訪問在該基類中被聲明（或繼承）的數(shù)據(jù)成員和成員函數(shù)（包括虛擬成員函數(shù)），而與它可能指向的實際對象無關(guān)，所以如果需要用基類指針來訪問一個沒有在該基類中聲明但是又在其派生類中定義了的成員，則需要執(zhí)行dynamic_cast來完成從基類指針到派生類指針的安全向下轉(zhuǎn)換。把一個成員聲明為虛擬的，只推延了“在程序執(zhí)行期間根據(jù)指針指向的實際類類型，對于要調(diào)用實例的解析過程”

 

3、 關(guān)于基類，派生類的相關(guān)補充：

1、 派生表中指定的類必須先被定義好，方可被指定為基類。

2、 派生類的前向聲明不能包括其派生表，而只需要類名即可。

3、 缺省的繼承是private。

4、 繼承而來的派生類的虛擬函數(shù)一般加上virtual較好，也可以省略。但基類中一定要聲明為virtual。

5、 對于基類的靜態(tài)成員，所有派生類對象都引用基類創(chuàng)建的這個相同，單一，共享的靜態(tài)成員，而不是創(chuàng)建該派生類的另一個獨立的靜態(tài)成員。

6、 友員關(guān)系不會被繼承，派生類沒有成為“向它的基類授權(quán)友誼的類”的友員。

 

4、 繼承機制下，派生類對象的構(gòu)造函數(shù)（析構(gòu)函數(shù)）調(diào)用順序為：

1、 基類（子對象的）構(gòu)造函數(shù)，若有多個基類，則以類派生表中出現(xiàn)的順序為序。

2、 成員類對象的構(gòu)造函數(shù)，若有多個成員類對象，則以它們在類定義中被聲明的順序為序。

3、派生類自己的構(gòu)造函數(shù)。

4、派生類對象的析構(gòu)函數(shù)的調(diào)用順序與它的構(gòu)造函數(shù)相反。繼承機制下，析構(gòu)函數(shù)的行為如下：派生類的析構(gòu)函數(shù)先被調(diào)用，再靜態(tài)調(diào)用基類的析構(gòu)函數(shù)（從直接基類開始）。注意一般基類的析構(gòu)函數(shù)不應(yīng)該是protected，因為虛擬函數(shù)承接了“調(diào)用者所屬類類型的訪問級別”。作為一般規(guī)則，我們建議將類層次結(jié)構(gòu)的根基類（聲明了一個或多個虛擬函數(shù)）的析構(gòu)函數(shù)聲明為虛擬的。

 

5、 關(guān)于繼承機制下基類構(gòu)造函數(shù)（析構(gòu)函數(shù)）相關(guān)的幾點說明：

1、 作為一般規(guī)則，派生類構(gòu)造函數(shù)應(yīng)不能直接向一個基類的數(shù)據(jù)成員賦值，而是要把值傳遞給適當?shù)幕悩?gòu)造函數(shù)來達到初始化賦值的目的。（一般是通過成員初始化表的方式）

2、 若基類不用于創(chuàng)建對象，則最好將其構(gòu)造函數(shù)放在protect區(qū)，只允許其派生類對象調(diào)用；若基類只允許創(chuàng)建某一個特定的派生類類型的對象，則應(yīng)該將基類的構(gòu)造函數(shù)放在private區(qū)，并將此特定的派生類聲明為該基類的友元來達到目的。

3、 派生類并不繼承基類的構(gòu)造函數(shù)，每個派生類都必須提供自己的構(gòu)造函數(shù)集，派生類的構(gòu)造函數(shù)只能合法的調(diào)用其直接基類的構(gòu)造函數(shù)。（注意這里虛擬繼承提供了一個特例：虛擬基類的初始化變成了最終派生類的責(zé)任）。

 

6、 關(guān)于虛擬函數(shù)的相關(guān)

1、 必須使用指針或者引用來支持虛擬函數(shù)機制（面向?qū)ο蟪绦蛟O(shè)計），基類對象由于其靜態(tài)編譯，故不會保留派生類的類型身份。

2、 第一次引入虛擬函數(shù)的基類時，必須在類體中將虛擬函數(shù)聲明為virtual，但若在該基類外部定義該虛擬函數(shù)時不能指定virtual。該基類的派生類中該虛擬函數(shù)virtual可加可不加，但從多重繼承考慮，最好加上。

3、 派生類改寫的基類虛擬函數(shù)，其原型必須與基類虛擬函數(shù)完全匹配（包括const和返回值），但返回值有個特例：派生類實例的返回值可以是基類實例返回類型的公有派生類類型。

4、 純虛擬函數(shù)（聲明后緊跟=0，函數(shù)定義可寫可不寫）只是提供了一個可被其派生類改寫的接口，其本身不能通過虛擬機制被調(diào)用，但可以靜態(tài)調(diào)用（寫了函數(shù)定義的虛基類的純虛擬函數(shù)）。一般來說，虛擬函數(shù)的靜態(tài)調(diào)用的目的是為了效率（避免動態(tài)綁定）。

5、 包含（或繼承）了一個或多個純虛擬函數(shù)的類被編譯器識別為抽象基類，抽象基類不能用來創(chuàng)建獨立的類對象，只能作為子對象出現(xiàn)在后續(xù)的派生類中。

6、通過基類指針來調(diào)用的虛擬函數(shù)的真正實例是在運行時刻確定的。但傳給虛擬函數(shù)的缺省實參是在編譯時刻根據(jù)被調(diào)用函數(shù)的對象的類型決定的（也即是若通過基類指針或引用調(diào)用派生類實例的虛擬函數(shù)，則傳遞給它的缺省實參是由基類指定的）。

 

7、 虛擬繼承和多繼承相關(guān)：

1、 虛擬繼承主要實為了解決繼承了多個基類實例，但是只需要一份單獨的共享實例的情況。

2、 非虛擬派生中，派生類只能顯式的初始化其直接基類（即派生類只能調(diào)用其直接基類的構(gòu)造函數(shù)），而在虛擬派生中，虛擬基類的初始化變成了最終派生類的責(zé)任，這個最終派生類是由每個特定的類對象聲明來決定的，其非虛擬基類的初始化同非虛擬派生一樣，只能由其直接派生類完成。（即中間派生類的對于虛擬基類構(gòu)造函數(shù)的調(diào)用被抑制）。

3、 虛擬繼承下構(gòu)造函數(shù)的調(diào)用順序按直接基類的聲明順序，對每個繼承子樹作深度優(yōu)先遍歷。第一步按此順序調(diào)用所有虛擬基類的構(gòu)造函數(shù)；第二步按此順序調(diào)用非虛擬基類的構(gòu)造函數(shù)。析構(gòu)函數(shù)的調(diào)用順序與構(gòu)造函數(shù)相反。

4、 虛擬基類成員的可視性，對于虛擬基類成員的繼承比該成員后來重新定義的實例權(quán)值（優(yōu)先級）小，故特化的派生類實例名覆蓋了共享的虛擬基類的實例名。而在非虛擬派生下的解析引用過程，每個繼承得到的實例都有相同的權(quán)值（優(yōu)先級）。

5、 繼承下派生類的類域被嵌套在基類類域中，若一個名字在派生類域中沒有被解析出來，則編譯器在外圍基類域中查找該名字定義。在多繼承下，名字解析查找過程為先是在本類類域中查找，再對繼承子樹中的所有基類同時查找，每個繼承得到的實例都有相同的權(quán)值（優(yōu)先級）。若在兩個或多個基類子樹中都找到了該名字，則對其的使用是二義的。

     摘要: 一、      什么是設(shè)計模式。 毫無疑問，設(shè)計模式是前人總結(jié)下來，一些設(shè)計經(jīng)驗經(jīng)過被反復(fù)使用、并為多數(shù)人知曉、經(jīng)過分類編目。模式是一種問題的解決思路，它已經(jīng)適用于一個實踐環(huán)境，并且可以適用于其他壞境。 最終由GoF總結(jié)出23種設(shè)計模式。 二、      為什么要使用。 根本原因是為了代碼復(fù)...  閱讀全文      摘要: 1、什么是Bridge模式？這個問題我用一言兩語實在無法概括其根本。不過我是這樣分析的：①、對象這個概念可以認為是由“屬性”和“行為”兩個部分組成的。屬性我們可以認為是一種靜止的，是一種抽象；一般情況下，行為是包含在一個對象中，但是，在有的情況下，我們需要將這些行為也進行歸類，形成一個總的行為接口，這就是橋模式的用處。②、Br...  閱讀全文