首先，本人非常承認用匯編語言實現二叉堆是很白癡的做法，也是非常吃力不討好的做法。不過貌似俺自己覺得接近了發燒友的程度了，所以有時發燒，這次寫了幾個匯編程序，包括二叉堆、快速排序、計數排序。然后就告一段落了，因為實在有多余覺得，不過有興趣的同學可以來討論一下呢，我是非常歡迎的。

目錄

第一章 什么是二叉堆4

1.1 二叉堆的結構和存儲4

1.2 二叉堆的操作4

第二章 關鍵匯編指令5

2.1 數據傳送5

2.1.1 MOV5

2.1.2 LDR5

2.1.3 STR5

2.2 算數和邏輯運算6

2.2.1 ADD6

2.2.2 LSL6

2.3 跳轉6

2.3.1 B6

2.3.2 BL7

第三章 匯編與C語言相互調用7

3.1 C語言調用匯編7

3.1.1 匯編子程序的返回7

3.1.2 匯編子程序的參數8

3.2 匯編調用C語言8

第四章 匯編實現二叉堆9

4.1、二叉堆最大化 - ASM_BiHeap_Maxify9

4.1.1 二叉堆最大化的作用9

4.1.2 二叉堆最大化的偽代碼9

4.1.3 二叉堆最大化C語言原形和解釋10

4.1.4 二叉堆最大化匯編語言描述10

4.2、二叉堆建立 - ASM_BiHeap_Build12

4.2.1 二叉堆建立的作用12

4.2.2 二叉堆建立的偽代碼12

4.2.3 二叉堆建立的C語言原形和解釋12

4.2.4 二叉堆建立的匯編語言描述13

4.3、二叉堆排序 - ASM_BiHeap_Sort13

4.3.1 二叉堆排序的作用13

4.3.2 二叉堆排序的偽代碼13

4.3.3 二叉堆最大化的C語言原形和解釋14

4.3.4 二叉堆最大化的匯編語言描述14

4.4、二叉堆鍵值增加 - ASM_BiHeap_KeyInc15

4.4.1 二叉堆鍵值增加的作用15

4.4.2 二叉堆鍵值增加的偽代碼15

4.4.3 二叉堆鍵值增加的C語言原形和解釋16

4.4.4 二叉堆鍵值增加的匯編語言描述16

4.5、二叉堆元素插入 - ASM_BiHeap_Insert17

4.5.1 二叉堆元素插入的作用17

4.5.2 二叉堆元素插入的偽代碼17

4.5.3 二叉堆元素插入的C語言原形和解釋17

4.5.4 二叉堆元素插入的匯編語言描述18

4.6、二叉堆最大元素 - ASM_BiHeap_Maximum18

4.6.1 二叉堆最大元素的作用18

4.6.2 二叉堆最大元素的偽代碼18

4.6.3 二叉堆最大元素的C語言原形和解釋19

4.6.4 二叉堆最大元素的匯編語言描述19

4.7、二叉堆出隊最大元素 - ASM_BiHeap_ExtraMax19

4.7.1 二叉堆出隊最大元素的作用19

4.7.2 二叉堆出隊最大元素的偽代碼19

4.7.3 二叉堆出隊最大元素的C語言原形和解釋20

4.7.4 二叉堆出隊最大元素的匯編語言描述20

第五章 測試21

5.1 匯編文件的包裝21

5.2 C語言頭文件22

5.3 測試23

5.4 測試結果24

附錄24

參考文獻24

  數據結構方面的知識，可以參考有關數據結構的書，我這里參考的是《算法導論》第二版，大家有興趣的話也可以參考一下。這一章介紹的是二叉堆。

  有很多數據結構，從鏈表到樹到圖，二叉堆算是樹的一種吧，這里我們討論的是最大堆，需要借用《算法導論》的原文來說明什么是二叉堆。先看圖：

  左圖 二叉堆的結構                        右圖 二叉堆的存儲。

  我們先看看結構，是層次型的。處在上層的節點的值大于下面節點的值，比如1（16）大于2（14）和3（10），這樣的堆我們稱為最大堆。

  存儲的話，編號為1點節點存儲在第1個位置，編號為2的節點存儲在第2個位置，以此類推。屬于順序存儲。

  我們存儲在計算機上的二叉堆是類似于C語言的數組，并且本人編程實現時（C語言和匯編語言）是將第0號位置用于存儲二叉堆的大小，即存儲的是二叉堆有多少個元素。比如上面的第0號位置存儲的是10，因為有10個元素。

  了解了二叉堆的結構和存儲，我們來看一下二叉堆支持什么操作。

二叉堆這種數據結構需要支持的操作分別有：

1、二叉堆最大化 - ASM_BiHeap_Maxify

2、二叉堆建立 - ASM_BiHeap_Build

3、二叉堆排序 - ASM_BiHeap_Sort

4、二叉堆鍵值增加 - ASM_BiHeap_KeyInc

5、二叉堆元素插入 - ASM_BiHeap_Insert

6、二叉堆最大元素 - ASM_BiHeap_Maximum

7、二叉堆出隊最大元素 - ASM_BiHeap_ExtraMax

  對應的這些操作在具體實現的時候會具體說明，當然，我們使用的是Cortex-M3匯編語言實現的。

  需要注意的是，我們是用C語言調用這些操作的。也就是說源代碼用匯編寫，但是留出C語言接口，讓C語言調用這些函數，這里我們初步了解一下，具體實現下面再做介紹。

  接下來因為是使用匯編語言，所以也大概介紹一下關鍵的匯編指令。

  匯編語言可能大家不是很熟悉，不過本人的話，從大二第二學期到大四第一學期，上課的話，每個學期都有涉及匯編指令，匯編程序。具體是從微機原理 -> 單片機原理 -> DSP原理 -> 嵌入式系統，呵呵，接觸了兩年多的會匯編，也該有點感覺了吧。這章介紹一點匯編指令，具體是參考《Cortex M3權威指南》。有一點要注意的是，對于匯編語言來說，在分號（;）后面是注釋，類似于C語言的行注釋（//）。

  這里的數據傳送包括寄存器與寄存器之間的數據傳送和寄存器與存儲器之間的數據傳送，介紹三個指令MOV，LDR，STR。

  可以說最經典的匯編指令就是MOV了，因為貌似連助記符都沒有變過，在眾多的微處理器中都是采用助記符MOV。下面舉個例子：

  MOV  R0,  R1    ;將R1寄存器的值復制到R0

相當簡單的匯編指令，看注釋就知道是什么意思了（分號后面的內容是注釋）。

  這個算數據加載吧，跟存儲器相關的數據傳送。本人理解為LoaD Register，大寫字母組成縮寫LDR，就是將存儲器ROM或者RAM的數據傳送到寄存器，舉個例子：

  LDR  R0,  [R1]    ;相當于C語言的R0 = *(unsigned int *)R1;

就是把R1當成地址，將R1指向的那個地址對應的數據傳送到R0。需要引起注意的是，這個指令一般是操作RAM或者ROM數據。

  這個算數據存儲吧，也是跟存儲器相關的數據傳送，只不過方向跟LDR相反。本人理解為STore Register，大寫字母組成縮寫STR，就是將寄存器的數據存儲到RAM或者ROM里面（現在的ROM很多都支持在線編程，比如Flash）。舉個例子：

  STR  R0,  [R1]    ;相當于C語言的*(unsigned int *)R1 = R0;

就是把R1當成地址，將R0的內容存儲到R1所指向的那個地址的存儲器上。同樣需要引起注意的是，這個指令一般也是操作RAM或者ROM數據。

  算數包括基本的加減乘除，邏輯運算是與或非位移等，這里介紹兩個最簡單的ADD和LSL。其他指令類似。

  加法指令，實現兩個數據相加，結果存儲到寄存器中。對應的還有減法指令SUB，乘法指令MUL，除法指令DIV。例子：

  ADD  R0,  R1    ;相當于C語言的R0 = R0 + R1或者R0 += R1

實現將R0 + R1兩個值相加，結果放在R0。

  邏輯左移指令，實現數據的邏輯左移。本人的理解為Logic Shift Left，大寫字母對應的縮寫為LSL。對應的有邏輯右移LSR，算數右移ASR等，這里只介紹LSL，例子：

  LSL  R0,  #2    ;相當于C語言的R0 = R0 << 2 或者R0 <<= 2;

實現將R0左移兩位，結果存放在R0，當然一般情況下會與LDR配合使用，可能稍微有一點點復雜了，例子：

  LDR  R0,  [R1, R2, LSL #2]    ;相當于C語言R0 = *(unsigned int *)(R1 + ( R2 << 2 ) );

將R1與R2左移兩位的值相加，作為地址，取該地址的數據傳送到R0。

  跳轉實現與PC相關的操作，改變程序的流程，這里介紹到是B，BL。

  這個指令的助記符就一個字母B，Branch，分支的意思，就是程序有兩個方向可以執行，選擇其中一個分支。例子：

  B  ASM_Loop    ;跳轉到ASM_Loop那里，ASM_Loop是一個標號

也就是程序的跳轉，并且是無條件跳轉，對應的有條件跳轉，再舉個條件跳轉到例子，對應的指令是BEQ，本人理解Branch EQual，大寫字母對應的縮寫為BEQ。

  BEQ ASM_Loop    ;在執行該指令前，一般執行CMP比較兩個數據

如果上一次比較兩個數據相等，就跳轉到ASM_Loop那里，如果不相等，不跳轉，也就是這條指令執行完后，程序流程沒有改變，依然是順序執行。跳轉與不跳轉對應的是兩個分支，也就應驗了Branch是分支的意思了。

  這個是Branch and Link，其中的Branch與上個指令的Branch是一樣的，分支，但是多了一個Link。意思是跳轉前，保存了PC+4到LR寄存器。LR是Link Register，其中LR的L與BL的L是同個意思，Link。

  多了這一步保存PC+4到LR的作用是可以實現程序返回，相當于C語言的子程序返回，比如我們有個C語言函數func，那么函數調用func()操作，在func函數執行完后可以返回調用該函數的程序那里繼續執行，這就是BL發揮了作用。例子：

  BL  ASM_My_Func    ;相當于C語言的ASM_My_Func()，函數調用，調用完會返回。

其中ASM_My_Func是一個匯編標號，或者是C語言函數，根本上來說就是一個地址。

  介紹了這些基本的指令，當然是遠遠不夠的，還是要看看《Cortex M3權威指南》才能有更深入的了解。有興趣的同學可以閱讀這個資料。接下來介紹匯編語言與C語言的混合編程。

  一般情況下我們都是用C語言編程的，但是也有不得不用到匯編的時候，就出現了C語言程序調用匯編子程序的問題。然而我們這里也會再介紹一下，相反的過程，就是匯編程序調用C語言子程序。

  模仿C語言的函數，將匯編程序寫成類似于C語言的函數，也就是需要返回，繼續執行前面的程序。并且有時候還需要帶有參數，帶有返回值，與C語言交互。下面一一介紹。

  指令B和BL都能實現跳轉，其中BL保存了下一條指令地址（PC+4）到LR，所以我們根據LR可以返回，返回操作指令具體是BX  LR。指令將LR值賦給PC，實現程序的返回，看下面的例子：

ASM_Func

  MOV  R0,  R1

  BX    LR

ASM_Func_End

  這就是一個匯編子程序了，只有兩條指令。第一條指令將R1復制到R0，第二條指令就是實現子程序的返回了。想要在C語言中調用這個匯編子程序，還需要做一些工作。

1、將標號ASM_Func聲明為外部的

2、C語言的頭文件聲明ASM_Func函數

3、C語言的源文件調用ASM_Func函數

具體怎么做分別如下：

1、在匯編文件中添加 EXPORT ASM_Func

2、C語言頭文件添加 void ASM_Func(void);

3、C語言源文件添加 ASM_Func(); （實現程序調用）

  這樣做就可以了，當然還有其他一些小工作，比如匯編文件末尾要有END，要聲明匯編文件的段啊什么的，具體后面介紹。上面的程序是沒有參數的，也就是C語言沒有傳遞參數給匯編子程序，匯編子程序也沒有返回參數給函數調用者。下面看看C語言怎么傳遞參數給匯編子程序，也就是準備函數間的通信啦。

  這一小節需要參考的是ATPCS，是ARM官方資料，講的是匯編與C語言之間參數的傳遞，我這里只是簡單介紹。

  首先傳進匯編子程序的參數，按照C語言函數調用是參數從左到右分別放在R0，R1，R2，R3，再到棧，如果有這么多參數的話，當然如果沒有這么多參數，比如只有兩個參數，就分別放在R0，R1了，以此類推。

  然后是返回給C語言的返回值，有返回值的話放在R0，沒有的話就不管R0是什么值了，因為C語言并不會用到。下面舉個簡單的例子：

ASM_Add

  ADD  R0,  R1

  BX   LR

ASM_Add_End

這個函數實現兩個數相加，返回相加的結果，類似于C語言的函數：

Int ASM_Add(int a, int b)

{

  Return a + b;

}

也就是匯編函數和C語言函數實現的是同樣的功能，只不過用不同編程語言實現而已。跟上面介紹的沒有參數的函數一樣，也是要做一些工作C語言才能順利調用這個函數的，老樣子列出來：

1、將標號ASM_Add聲明為外部的

2、C語言的頭文件聲明ASM_Add函數

3、C語言的源文件調用ASM_Add函數

具體怎么做分別如下：

1、在匯編文件中添加 EXPORT ASM_Add

2、C語言頭文件添加 void ASM_Add(int a, int b);

3、C語言源文件添加 ASM_Func(3, 2);

  這樣的話我們就可以實現在C語言中靈活的調用匯編子程序了，接下來是相反的過程，匯編程序調用C語言子程序。

  如果我們用匯編實現類似于C語言的malloc函數，那真的是更加的吃力不討好了，所以有時候我們也可以在匯編中調用已有的C語言函數，方便我們的程序開發。下面也通過一個例子介紹：

  匯編語言調用一個C語言函數func()，比如func()函數是這樣子的

Int func(int a, int b)

{

  Return a + b;

}

  那么匯編語言調用時的參數從R0，R1，R2，R3到棧傳遞，返回值也是在R0取。調用實例如下：

MOV  R1,  #2

MOV  R2,  #3

BL    Func      ;調用C語言函數

...               ;這時候R0已經是5了

  當然，為了讓匯編程序能知道Func標號，需要在文件前面添加IMPORT Func才能成功編譯鏈接。

  可以看到匯編語言和C語言編程也是比較方便等，有了上面這些基礎知識，下面我們開始介紹具體怎么用匯編語言實現二叉堆了，測試程序的話用C語言編寫，因為我們重點是實現匯編子程序而不是整個工程。

  我們實現的幾個接口函數在第一章講過，函數原形也是在第一章就給出了，這一章是具體實現了。這里分別給出操作的作用，然后給出偽代碼，再給出C語言的函數原形和解釋，最后給出Cortex-M3的匯編語言描述。再次說明，本人參考的是《算法導論》第二版，所以偽代碼是來自算法導論的。

  二叉堆最大化是一個子程序，被其他二叉堆操作調用。其作用是保持二叉堆的性質，即父節點的值大于子節點的值，然后遞歸下去。

  需要注意的是這個函數是遞歸的，也就是第10行調用的函數就是本函數，具體看截圖：

  C語言原形：void  ASM_BiHeap_Maxify( uint32_t  *BiHeap,  uint32_t  i );

  其中BiHeap是指向二叉堆的指針，也就是二叉堆的首地址，我們這里是一個數組的首地址，i是二叉堆元素的位置，該操作實現將二叉堆中以i為根的二叉堆保持二叉堆的性質（父節點的值大于子節點的值）。

  再次說明，二叉堆的大小（二叉堆元素的個數）是存儲在BiHeap數組的第0個位置，也就是heap-size[BiHeap]相當于C語言的BiHeap[0]。

  偽代碼的意思是：

1、找到第i個節點的值，比較其與左右子節點的值的大小

2、獲取最大值的位置存放在largest

3、比較largest與i

  不同：交換largest與i對應位置的元素值，遞歸調用本函數最大化largest

  相同：不需要操作，退出

這樣就實現而二叉堆的最大化，還不明白的同學請網上找資料，我們這里的重點是用匯編語言實現上面的偽代碼。

  匯編語言也是根據偽代碼編寫出來的，所以先理解偽代碼才對，具體代碼如下：

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_Maxify

;   描述    :   二叉堆最大化

;   輸入    :   R0  --- 二叉堆首地址

;               R1  --- 二叉堆父節點偏移

;   輸出    :   無

;   寄存器  :   使用R1 ~ R8

;   調用    :   內部調用

;*****************************  *******************************

ASM_BiHeap_Maxify

    PUSH    {LR}

    MOV     R2,         R1                       ;R1為父節點偏移

    ADD     R2,         R2                       ;R2為左孩子偏移

    ADD     R3,         R2,                 #1    ;R3為右孩子偏移

    MOV     R4,         R1                       ;R4為最大節偏移

    LDR     R5,         [R0, R1, LSL #2]            ;R5為最大節點值

    LDR     R6,         [R0]                      ;R6為二叉堆大小

    CMP     R2,         R6                        ;判斷是否有左孩子

    BGT     AMS_BiHeap_Maxify_Exit                ;沒有左孩子, 退出

    LDR     R7,         [R0, R2, LSL #2]            ;R7為左孩子節點

    CMP     R7,         R5                       ;比較節點大小

    ITT     GT                                   ;如果違反最大堆規則

    MOVGT   R4,         R2                      ;左孩子值大于父節點值, 更新R4

    MOVGT   R5,         R7                      ;更新最大值R5

    CMP     R3,         R6                      ;判斷是否有右孩子

    BGT     ASM_BiHeap_Maxify_Judge            ;沒有右孩子, 退出

    LDR     R7,         [R0, R3, LSL #2]          ;R7為右孩子節點

    CMP     R7,         R5                      ;比較節點大小

    IT      GT                                  ;如果違反最大堆規則

    MOVGT   R4,         R3                    ;右孩子值大于父節點值, 更新R4

    MOVGT   R5,         R7                    ;更新最大值R5

ASM_BiHeap_Maxify_Judge

    CMP     R1,         R4                     ;如果父節是, 不違反二叉堆規則

    BEQ     AMS_BiHeap_Maxify_Exit             ;退出

ASM_BiHeap_Maxify_Exchange

    LDR     R7,         [R0, R1, LSL #2]          ;取父節點值

    STR     R5,         [R0, R1, LSL #2]          ;交換

    STR     R7,         [R0, R4, LSL #2]          ;交換

    MOV     R1,         R4                    ;R1作為父節點, 遞歸二叉堆最大化

    BL      ASM_BiHeap_Maxify                 ;遞歸

AMS_BiHeap_Maxify_Exit   

    POP     {PC}                               ;退出

ASM_BiHeap_Maxify_End

  本人非常承認偽代碼確實也有點長，比起C語言編寫的函數，實在是吃力不討好，連本人自己看著注釋都有點覺得難懂，不過如果想看懂匯編語言的話先要非常清楚的知道幾個寄存器存放的是什么，再次羅列出來：

;R1為父節點偏移

;R2為左孩子偏移

;R3為右孩子偏移

;R4為最大節偏移

;R5為最大節點值

;R6為二叉堆大小

  只要清楚的認識這幾個寄存器的作用就好多了，不會很暈。參考偽代碼和寄存器作用的注釋，就比較容易看懂這個匯編了。在這里先告訴大家一個好消息是，這個函數是最復雜的，下面的幾個操作調用這個函數的話，就顯得很簡潔易懂了。

  我們把一個普通的數組構建成一個二叉堆，調用的就是二叉堆建立函數，可見，二叉堆的建立不改變數據的存儲，仍然是一個數組，但是改變了數據的結構，變成層次型了。

  可以看到非常簡潔的偽代碼，驗證了剛才說的，調用二叉堆最大化子程序，可以把二叉堆其他操作的實現變得很簡潔。

  C語言原形：void  ASM_BiHeap_Build( uint32_t  *BiHeap );

  老樣子，BiHeap是二叉堆首地址，調用該函數實現二叉堆的建立，把一個普通的數組建立成一個二叉堆，之后我們就可以對二叉堆實現二叉堆特有的各種操作了。

  偽代碼解釋：

1、獲取二叉堆的大小，保存在heap-size[A]中

2、把數組平均劃分成兩個部分，前半部分和后半部分

3、對前半部分，從Length[A]/2到1，循環調用MAX_Heapify，也就是我們上節實現的二叉堆最大化。

  這樣就實現了二叉堆的建立。通俗一點，舉個例子是數組有10個元素，我們從5（一半）到1，循環調用二叉堆最大化，至于為什么這么做能實現二叉堆最大化，大家如果不明白的話網上找資料吧。

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_Build

;   描述    :   二叉堆構建

;   輸入    :   R0  --- 二叉堆首地址

;   輸出    :   無

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_Build

    PUSH    {R1, LR}

    LDR     R1,         [R0]                        ;R1為二叉堆大小

    LSR     R1,         #1                          ;二叉堆需要最大化個數

ASM_BiHeap_Build_Loop

    PUSH    {R1-R8}                                 ;入棧

    BL      ASM_BiHeap_Maxify                       ;二叉堆最大化

    POP     {R1-R8}                                  ;出棧

    SUB     R1,         #1                          ;遞減二叉堆最大化個數

    CMP     R1,         #0                          ;判斷是否為零

    BNE     ASM_BiHeap_Build_Loop                  ;不為零, 繼續循環

    POP     {R1, PC}                                 ;返回

ASM_BiHeap_Build_End

  老樣子先看懂偽代碼，再順著代碼，看注釋是比較容易理解的，接下來繼續其他操作。

  二叉堆的排序算是二叉堆的一個附加操作了，因為排序后二叉堆就已經不是二叉堆的結構了，而是一個按值的大小排序的數組了。

  偽代碼依然是這么的簡潔，同樣也調用了二叉堆最大化子程序。

  C語言原形：void  ASM_BiHeap_Sort( uint32_t  *BiHeap );

  偽代碼解釋：

1、建立二叉堆

2、循環執行Length[A]-1次，每次的操作包含以下：

  3、改變循環變量i，從Length[A]到2

  4、交換第一個元素（最大值）與第i個元素的值（交換后最后一個元素是最大值）

  5、二叉堆元素個數減一

  6、最大化二叉堆，保持二叉堆性質（因為交換了第一個元素和第i個元素值，父節點可能不是最大值）

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_Sort

;   描述    :   二叉堆排序

;   輸入    :   R0  --- 二叉堆首地址

;   輸出    :   無

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_Sort

    PUSH    {R1-R4, LR}

    BL      ASM_BiHeap_Build                        ;建立二叉堆

    LDR     R1,         [R0]                        ;R1存放二叉堆大小

    PUSH    {R1}   

ASM_BiHeap_Sort_Loop

    LDR     R3,         [R0, #4]                    ;R2為二叉堆首元素

    LDR     R4,         [R0, R1, LSL #2]            ;R3為二叉堆最后一個元素

    STR     R3,         [R0, R1, LSL #2]            ;最大元素放在二叉堆末尾

    STR     R4,         [R0, #4]                    ;二叉堆末尾元素放在二叉堆首

    SUB     R1,         #1                         ;二叉堆元素個數減一

    STR     R1,         [R0]                       ;保存二叉堆元素個數

    PUSH    {R1-R8}                               ;入棧

    MOV     R1,         #1                        ;R1為待最大化二叉堆元素

    BL      ASM_BiHeap_Maxify                     ;二叉堆最大化

    POP     {R1-R8}                                ;出棧

    CMP     R1,         #0                         ;比較二叉堆元素是否為零

    BNE     ASM_BiHeap_Sort_Loop                  ;不為零, 繼續排序

    POP     {R1}                                   ;出棧二叉堆大小

    STR     R1,         [R0]                        ;重新賦值二叉堆大小

    POP     {R1-R4, PC}                            ;返回

ASM_BiHeap_Sort_End

  也是從偽代碼到匯編代碼和注釋這樣看。進入下一個操作。

  二叉堆鍵值增加實現二叉堆元素值增加，可以實現優先級隊列，算是優先級隊列的一個操作吧，增加對應的優先級。

  也是很簡潔，但是這次沒有調用二叉堆最大化子程序。

  C語言原形：

void  ASM_BiHeap_KeyInc( uint32_t *BiHeap,  uint32_t Pos,  uint32_t NewKey );

  偽代碼解釋：

1、如果鍵值小于原來的鍵值

  2、退出

3、賦值新的鍵值（有可能破壞二叉堆結構，新鍵值可能大于父節點值）

4、循環保持二叉堆性質

  5、循環條件為i大于根節點位置，并且父節點值小于子節點值

  6、交換父節點值與子節點值

  7、修改i的位置為父節點位置（繼續循環，回到4，因為有可能二叉堆性質被破壞）,

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_KeyInc

;   描述    :   二叉堆指定元素鍵值更新

;   輸入    :   R0  --- 二叉堆首地址

;               R1  --- 指定元素偏移

;               R2  --- 新鍵值

;   輸出    :   無

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_KeyInc

    PUSH    {R3-R4, LR}

    LDR     R3,         [R0, R1, LSL #2]            ;R3為指定元素值

    CMP     R3,         R2                       ;比較指定元素與新元素大小

    BGT     ASM_BiHeap_KeyInc_Exit               ;指定元素更大, 退出

    STR     R2,         [R0, R1, LSL #2]            ;保存新元素到指定元素

    MOV     R3,         R1,                 LSR #1 ;R3為父節點偏移

    CMP     R3,         #0                         ;如果父節點是否大于零

    BEQ     ASM_BiHeap_KeyInc_Exit                 ;為零, 退出

ASM_BiHeap_KeyInc_Loop

    LDR     R4,         [R0, R3, LSL #2]             ;R4為父節點元素

    CMP     R4,         R2                         ;比較父節點元素與新元素

    BGT     ASM_BiHeap_KeyInc_Exit              ;父節點大, 滿足二叉堆規則, 退出

    STR     R4,         [R0, R1, LSL #2]              ;小元素放在子節點

    STR     R2,         [R0, R3, LSL #2]              ;大元素放在父節點

    MOV     R4,         R2                         ;更新子節點偏移

    MOV     R1,         R3                         ;

    LSR     R3,         #1                          ;更新父節點偏移

    CMP     R3,         #0                          ;如果父節點是否大于零

    BGT     ASM_BiHeap_KeyInc_Loop                ;大于零, 繼續循環

ASM_BiHeap_KeyInc_Exit

    POP     {R3-R4, PC}                             ;返回

ASM_BiHeap_KeyInc_End

  看懂程序 == 偽代碼 + 匯編代碼 + 注釋，接下來進入下一個操作。

  插入新元素是一種非常常見的操作，二叉堆當然也支持這種操作，可以理解為添加一個新成員吧。

  調用了二叉堆鍵值增加子程序，代碼更加簡潔了。

  C語言原形：void  ASM_BiHeap_KeyInsert (uint32_t *BiHeap,  uint32_t Key) ;

  偽代碼解釋：

1、二叉堆元素個數加一（因為插入了一個新元素）

2、新元素賦值為負無窮，實際我們用一個很小的數代替

3、調用鍵值增加子程序實現對應元素的賦值（保持了二叉堆的性質）

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_KeyInsert

;   描述    :   二叉堆元素插入

;   輸入    :   R0  --- 二叉堆首地址

;               R1  --- 新元素鍵值

;   輸出    :   無

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_KeyInsert

    PUSH    {R2-R3, LR}

    LDR     R2,         [R0]                      ;二叉堆大小

    ADD     R2,         #1                       ;二叉堆大小加一

    STR     R2,         [R0]                      ;更新二叉堆大小

    MOV     R3,         #0                       ;R3為0

    STR     R3,         [R0, R2, LSL #2]            ;新元素值為0

    MOV     R3,         R2                       ;R3為新元素位置

    MOV     R2,         R1                       ;R2為新元素值

    MOV     R1,         R3                       ;R1為新元素位置

    BL      ASM_BiHeap_KeyInc                    ;調用二叉堆指定元素鍵值更新

    POP     {R2-R3, PC}                            ;返回

ASM_BiHeap_KeyInsert_End

  看懂程序 == 偽代碼 + 匯編代碼 + 注釋，接下來進入下一個操作。

  查詢二叉堆中最大的元素使用的操作，比較簡單。

  C語言原形：uint32_t  ASM_BiHeap_Maximum( uint32_t  *BiHeap );

  偽代碼解釋：直接返回位置為1的元素

  可以說這是最簡單的操作了，代碼：

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_Maximum

;   描述    :   二叉堆返回最大元素

;   輸入    :   R0          --- 二叉堆首地址

;   輸出    :   uint32_t    --- 二叉堆最大元素

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_Maximum

    LDR     R0,         [R0, #4]                    ;獲取二叉堆首元素

    BX      LR                                    ;返回

ASM_BiHeap_Maximum_End

  接下來下一個操作，也是最后一個操作了。

  出隊實現了返回最大元素的功能，同時將元素從二叉堆移除，也就是出隊后二叉堆就沒有了這個元素。

  還是調用了二叉堆最大化子程序，變得很簡潔了。

  C語言原形：uint32_t  ASM_BiHeap_ExtracMax( uint32_t  *Arr );

  偽代碼解釋：

1、如果二叉堆元素個數小于1，返回錯誤

2、把第1個元素（最大元素）放在max

3、最后一個元素放在第1個元素位置（覆蓋了第一個位置的值）

4、二叉堆元素個數減一（因為出隊）

5、調用二叉堆最大化子程序保持二叉堆性質（最后一個元素放在第一個，可能破壞二叉堆性質）

6、返回max（返回最大元素，同時最大元素也已經出隊了）

;*****************************  *******************************

;   函數名  :   ASM_BiHeap_ExtracMax

;   描述    :   二叉堆返回最大元素

;   輸入    :   R0          --- 二叉堆首地址

;   輸出    :   uint32_t    --- 二叉堆最大元素

;   寄存器  :   無

;   調用    :   外部調用

;*****************************  *******************************

ASM_BiHeap_ExtracMax

    PUSH    {R1-R2, LR}

    LDR     R1,         [R0, #4]        ;R1二叉堆最大元素

    PUSH    {R1}                      ;入棧保護最大元素

    LDR     R1,         [R0]           ;R1為二叉堆大小

    LDR     R2,         [R0, R1, LSL #2] ;R2為二叉堆最后一個元素

    STR     R2,         [R0, #4]        ;最后一個元素放在首元素, 破壞二叉堆結構

    SUB     R1,         #1             ;二叉堆元素個數減一

    STR     R1,         [R0]            ;保存二叉堆元素個數

    PUSH    {R2-R8}

    MOV     R1,         #1             ;二叉堆待最大化元素

    BL      ASM_BiHeap_Maxify          ;二叉堆最大化

    POP     {R2-R8}

    POP     {R0}                        ;最大元素放在R0

    POP     {R1-R2, PC}                 ;返回

ASM_BiHeap_ExtracMax_End

  看懂程序 == 偽代碼 + 匯編代碼 + 注釋，最后一個操作也完了。

  實現了這些操作之后，我們就開始編寫程序測試這些操作是否正確了，測試程序是用C語言編寫的，也就是用C語言調用匯編子程序。

  我們在上一章編寫的只是子程序，對一個匯編文件來說，跟C語言一樣也要包括其他偽指令啊宏定義啊什么的，這一節我們來看看這么做。需要的操作有：

1、代碼段聲明

2、聲明標號為外部的

3、添加END

具體整個文件應該是對應的一下形式：

;***************************** 接口函數聲明 *******************************

    EXPORT  ASM_BiHeap_Build                        ;二叉堆構建

    EXPORT  ASM_BiHeap_Sort                         ;二叉堆排序

    EXPORT  ASM_BiHeap_Maximum                    ;二叉堆返回最大元素

    EXPORT  ASM_BiHeap_ExtracMax                    ;二叉堆返回最大元素

    EXPORT  ASM_BiHeap_KeyInc                       ;二叉堆指定元素鍵值更新

    EXPORT  ASM_BiHeap_KeyInsert                    ;二叉堆元素插入

;*****************************  *******************************

;***************************** 代碼段聲明 *******************************

    AREA    |.text|,    CODE,   READONLY,   ALIGN=2

    THUMB

    REQUIRE8

    PRESERVE8

;*****************************  *******************************

;***************************** 代碼 *******************************

  匯編子程序

;*****************************  *******************************

    END

;**************************************文件結束****************************

  以上格式就是我們的匯編源文件，分別對應四個部分。

1、標號聲明

2、代碼段聲明

3、代碼段

4、END

  其中的匯編子程序就是上一章我們所實現的二叉堆的操作了。

  本人為了讓C語言能調用這些匯編函數，對應編寫了一個C語言的頭文件，聲明這些函數，具體實現如下：

#ifndef __BIHEAP_H

#define __BIHEAP_H

#include "stm32f10x.h"

void ASM_BiHeap_Maxify(uint32_t *Arr, uint32_t Len);               //二叉堆最大化

void ASM_BiHeap_Build(uint32_t *Arr);                           //二叉堆建立

void ASM_BiHeap_Sort(uint32_t *Arr);                            //二叉堆排序

void ASM_BiHeap_KeyInc(uint32_t *Arr, uint32_t Pos, uint32_t NewKey); //二叉堆鍵值增加

void ASM_BiHeap_KeyInsert(uint32_t *Arr, uint32_t Key);           //二叉堆元素插入

uint32_t ASM_BiHeap_Maximum(uint32_t *Arr);                   //二叉堆最大元素

uint32_t ASM_BiHeap_ExtracMax(uint32_t *Arr);                  //二叉堆出對最大元素

#endif  //#ifndef __BIHEAP_H

  對應的C語言測試源文件，這個函數并沒有測試所有的匯編子程序，不過本人自己都測試過了，這里只是舉個例子：

#include "data_struc.h"

#if BI_HEAP_TEST_EN                              //如果使能二叉堆測試

static uint32_t Arr[20] = {15, 1, 2, 3, 4, 5, 6, 7, 8,

9, 10, 11, 12, 13, 14, 15};                      //二叉堆, 首元素為二叉堆的元素個數

#endif  //#if BI_HEAP_TEST_EN

#if BI_HEAP_TEST_EN                              //如果使能二叉堆測試

FStat BiHeap_Test(void)

{

    ASM_BiHeap_Build( Arr );                     //構建二叉堆函數

    ASM_BiHeap_KeyInsert( Arr, 10);              //添加元素

    ASM_BiHeap_KeyInc( Arr, 2, 16 );             //指定元素鍵值增加

    printf("%d\n", ASM_BiHeap_ExtracMax( Arr ) );//打印出對元素

    return FuncOK;

}

#endif  //#if BI_HEAP_TEST_EN

  測試結果是本人認為是正確的，這里也不貼出來了，畢竟文章也比較長了。如果那里有錯誤歡迎大家指出來，感謝大家啦。

1、C語言的主函數

[1] 《算法導論》第二版  機械工業出版社

[2] 《Cortex-M3權威指南》 Joseph Yiu 著  宋巖 譯