1.程序內存分區(qū)中的堆與棧

1.1 棧簡介

棧由操作系統(tǒng)自動分配釋放 ，用于存放函數的參數值、局部變量等，其操作方式類似于數據結構中的棧。參考如下代碼：

int main() {
	int b;				//棧
	char s[] = "abc"; 	//棧
	char *p2;			//棧
}

其中函數中定義的局部變量按照先后定義的順序依次壓入棧中，也就是說相鄰變量的地址之間不會存在其它變量。棧的內存地址生長方向與堆相反，由高到底，所以后定義的變量地址低于先定義的變量，比如上面代碼中變量 s 的地址小于變量 b 的地址，p2 地址小于 s 的地址。棧中存儲的數據的生命周期隨著函數的執(zhí)行完成而結束。

1.2 堆簡介

堆由開發(fā)人員分配和釋放， 若開發(fā)人員不釋放，程序結束時由 OS 回收，分配方式類似于鏈表。參考如下代碼：

int main() {
	// C 中用 malloc() 函數申請
	char* p1 = (char *)malloc(10);
	cout<<(int*)p1<<endl;		//輸出：00000000003BA0C0
	// 用 free() 函數釋放
	free(p1);
	// C++ 中用 new 運算符申請
	char* p2 = new char[10];
	cout << (int*)p2 << endl;		//輸出：00000000003BA0C0
	// 用 delete 運算符釋放
	delete[] p2;
}

其中 p1 所指的 10 字節(jié)的內存空間與 p2 所指的 10 字節(jié)內存空間都是存在于堆。堆的內存地址生長方向與棧相反，由低到高，但需要注意的是，后申請的內存空間并不一定在先申請的內存空間的后面，即 p2 指向的地址并不一定大于 p1 所指向的內存地址，原因是先申請的內存空間一旦被釋放，后申請的內存空間則會利用先前被釋放的內存，從而導致先后分配的內存空間在地址上不存在先后關系。堆中存儲的數據若未釋放，則其生命周期等同于程序的生命周期。

關于堆上內存空間的分配過程，首先應該知道操作系統(tǒng)有一個記錄空閑內存地址的鏈表，當系統(tǒng)收到程序的申請時，會遍歷該鏈表，尋找第一個空間大于所申請空間的堆節(jié)點，然后將該節(jié)點從空閑節(jié)點鏈表中刪除，并將該節(jié)點的空間分配給程序。另外，對于大多數系統(tǒng)，會在這塊內存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確地釋放本內存空間。由于找到的堆節(jié)點的大小不一定正好等于申請的大小，系統(tǒng)會自動地將多余的那部分重新放入空閑鏈表。

1.3 堆與棧區(qū)別

堆與棧實際上是操作系統(tǒng)對進程占用的內存空間的兩種管理方式，主要有如下幾種區(qū)別：

（1）管理方式不同。棧由操作系統(tǒng)自動分配釋放，無需我們手動控制；堆的申請和釋放工作由程序員控制，容易產生內存泄漏；

（2）空間大小不同。每個進程擁有的棧的大小要遠遠小于堆的大小。理論上，程序員可申請的堆大小為虛擬內存的大小，進程棧的大小 64bits 的 Windows 默認 1MB，64bits 的 Linux 默認 10MB；

（3）生長方向不同。堆的生長方向向上，內存地址由低到高；棧的生長方向向下，內存地址由高到低。

（4）分配方式不同。堆都是動態(tài)分配的，沒有靜態(tài)分配的堆。棧有2種分配方式：靜態(tài)分配和動態(tài)分配。靜態(tài)分配是由操作系統(tǒng)完成的，比如局部變量的分配。動態(tài)分配由alloca函數進行分配，但是棧的動態(tài)分配和堆是不同的，他的動態(tài)分配是由操作系統(tǒng)進行釋放，無需我們手工實現(xiàn)。

（5）分配效率不同。棧由操作系統(tǒng)自動分配，會在硬件層級對棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執(zhí)行，這就決定了棧的效率比較高。堆則是由C/C++提供的庫函數或運算符來完成申請與管理，實現(xiàn)機制較為復雜，頻繁的內存申請容易產生內存碎片。顯然，堆的效率比棧要低得多。

（6）存放內容不同。棧存放的內容，函數返回地址、相關參數、局部變量和寄存器內容等。當主函數調用另外一個函數的時候，要對當前函數執(zhí)行斷點進行保存，需要使用棧來實現(xiàn)，首先入棧的是主函數下一條語句的地址，即擴展指針寄存器的內容（EIP），然后是當前棧幀的底部地址，即擴展基址指針寄存器內容（EBP），再然后是被調函數的實參等，一般情況下是按照從右向左的順序入棧，之后是被調函數的局部變量，注意靜態(tài)變量是存放在數據段或者BSS段，是不入棧的。出棧的順序正好相反，最終棧頂指向主函數下一條語句的地址，主程序又從該地址開始執(zhí)行。堆，一般情況堆頂使用一個字節(jié)的空間來存放堆的大小，而堆中具體存放內容是由程序員來填充的。

從以上可以看到，堆和棧相比，由于大量malloc()/free()或new/delete的使用，容易造成大量的內存碎片，并且可能引發(fā)用戶態(tài)和核心態(tài)的切換，效率較低。棧相比于堆，在程序中應用較為廣泛，最常見的是函數的調用過程由棧來實現(xiàn)，函數返回地址、EBP、實參和局部變量都采用棧的方式存放。雖然棧有眾多的好處，但是由于和堆相比不是那么靈活，有時候分配大量的內存空間，主要還是用堆。

無論是堆還是棧，在內存使用時都要防止非法越界，越界導致的非法內存訪問可能會摧毀程序的堆、棧數據，輕則導致程序運行處于不確定狀態(tài)，獲取不到預期結果，重則導致程序異常崩潰，這些都是我們編程時與內存打交道時應該注意的問題。

2.數據結構中的堆與棧

數據結構中，堆與棧是兩個常見的數據結構，理解二者的定義、用法與區(qū)別，能夠利用堆與棧解決很多實際問題。

2.1 棧簡介

棧是一種運算受限的線性表，其限制是指只僅允許在表的一端進行插入和刪除操作，這一端被稱為棧頂（Top），相對地，把另一端稱為棧底（Bottom）。把新元素放到棧頂元素的上面，使之成為新的棧頂元素稱作進棧、入棧或壓棧（Push）；把棧頂元素刪除，使其相鄰的元素成為新的棧頂元素稱作出?；蛲藯＃≒op）。這種受限的運算使棧擁有“先進后出”的特性（First In Last Out），簡稱FILO。

棧分順序棧和鏈式棧兩種。棧是一種線性結構，所以可以使用數組或鏈表（單向鏈表、雙向鏈表或循環(huán)鏈表）作為底層數據結構。使用數組實現(xiàn)的棧叫做順序棧，使用鏈表實現(xiàn)的棧叫做鏈式棧，二者的區(qū)別是順序棧中的元素地址連續(xù)，鏈式棧中的元素地址不連續(xù)。

棧的結構如下圖所示：

棧的基本操作包括初始化、判斷棧是否為空、入棧、出棧以及獲取棧頂元素等。下面以順序棧為例，使用 C++ 給出一個簡單的實現(xiàn)。

#include<stdio.h>
#include<malloc.h>
#define DataType int
#define MAXSIZE 1024
struct SeqStack {
	DataType data[MAXSIZE];
	int top;
};
//棧初始化,成功返回棧對象指針，失敗返回空指針NULL
SeqStack* initSeqStack() {
	SeqStack* s=(SeqStack*)malloc(sizeof(SeqStack));
	if(!s) {
		printf("空間不足\n");
		return NULL;
	} else {
		s->top = -1;
		return s;
	}
}
//判斷棧是否為空
bool isEmptySeqStack(SeqStack* s) {
	if (s->top == -1)
		return true;
	else
		return false;
}
//入棧，返回-1失敗，0成功
int pushSeqStack(SeqStack* s, DataType x) {
	if(s->top == MAXSIZE-1)
	{
		return -1;//棧滿不能入棧
	} else {
		s->top++;
		s->data[s->top] = x;
		return 0;
	}
}
//出棧，返回-1失敗，0成功
int popSeqStack(SeqStack* s, DataType* x) {
	if(isEmptySeqStack(s)) {
		return -1;//?？詹荒艹鰲?
	} else {
		*x = s->data[s->top];
		s->top--;
		return 0;
	}
}
//取棧頂元素，返回-1失敗，0成功
int topSeqStack(SeqStack* s,DataType* x) {
	if (isEmptySeqStack(s))
		return -1;	//?？?
	else {
		*x=s->data[s->top];
		return 0;
	}
}
//打印棧中元素
int printSeqStack(SeqStack* s) {
	int i;
	printf("當前棧中的元素:\n");
	for (i = s->top; i >= 0; i--)
		printf("%4d",s->data[i]);
	printf("\n");
	return 0;
}
//test
int main() {
	SeqStack* seqStack=initSeqStack();
	if(seqStack) {
		//將4、5、7分別入棧
		pushSeqStack(seqStack,4);
		pushSeqStack(seqStack,5);
		pushSeqStack(seqStack,7);
		//打印棧內所有元素
		printSeqStack(seqStack);
		//獲取棧頂元素
		DataType x=0;
		int ret=topSeqStack(seqStack,&x);
		if(0==ret) {
			printf("top element is %d\n",x);
		}
		//將棧頂元素出棧
		ret=popSeqStack(seqStack,&x);
		if(0==ret) {
			printf("pop top element is %d\n",x);
		}
	}
	return 0;
}

運行上面的程序，輸出結果：

當前棧中的元素:

7 5 4

top element is 7

pop top element is 7

2.2 堆簡介

2.2.1 堆的性質

堆是一種常用的樹形結構，是一種特殊的完全二叉樹，當且僅當滿足所有節(jié)點的值總是不大于或不小于其父節(jié)點的值的完全二叉樹被稱之為堆。堆的這一特性稱之為堆序性。因此，在一個堆中，根節(jié)點是最大（或最?。┕?jié)點。如果根節(jié)點最小，稱之為小頂堆（或小根堆），如果根節(jié)點最大，稱之為大頂堆（或大根堆）。堆的左右孩子沒有大小的順序。

下面是一個小頂堆示例：

堆的存儲一般都用數組來存儲堆，i節(jié)點的父節(jié)點下標就為 ( i – 1 ) / 2 (i – 1) / 2 (i–1)/2。它的左右子節(jié)點下標分別為 2 ∗ i + 1 2 * i + 1 2∗i+1 和 2 ∗ i + 2 2 * i + 2 2∗i+2。如第0個節(jié)點左右子節(jié)點下標分別為1和2。

2.2.2 堆的基本操作

（1）建立

以最小堆為例，如果以數組存儲元素時，一個數組具有對應的樹表示形式，但樹并不滿足堆的條件，需要重新排列元素，可以建立“堆化”的樹。

（2）插入

將一個新元素插入到表尾，即數組末尾時，如果新構成的二叉樹不滿足堆的性質，需要重新排列元素，下圖演示了插入15時，堆的調整。

（3）刪除。

堆排序中，刪除一個元素總是發(fā)生在堆頂，因為堆頂的元素是最小的（小頂堆中）。表中最后一個元素用來填補空缺位置，結果樹被更新以滿足堆條件。

2.2.3 堆操作實現(xiàn)

（1）插入代碼實現(xiàn)

每次插入都是將新數據放在數組最后。可以發(fā)現(xiàn)從這個新數據的父節(jié)點到根節(jié)點必然為一個有序的數列，現(xiàn)在的任務是將這個新數據插入到這個有序數據中，這就類似于直接插入排序中將一個數據并入到有序區(qū)間中，這是節(jié)點“上浮”調整。不難寫出插入一個新數據時堆的調整代碼：

// 新加入i節(jié)點,其父節(jié)點為(i-1)/2
// 參數：a：數組，i：新插入元素在數組中的下標  
void minHeapFixUp(int a[], int i) {  
    int j, temp;  
    temp = a[i];  
    j = (i-1)/2;      //父節(jié)點  
    while (j >= 0 && i != 0) {  
        if (a[j] <= temp)//如果父節(jié)點不大于新插入的元素，停止尋找  
            break;  
        a[i]=a[j];    		//把較大的子節(jié)點往下移動,替換它的子節(jié)點  
        i = j;  
        j = (i-1)/2;  
    }  
    a[i] = temp;  
}  

因此，插入數據到最小堆時：

// 在最小堆中加入新的數據data  
// a：數組，index：插入的下標，
void minHeapAddNumber(int a[], int index, int data) {  
    a[index] = data;  
    minHeapFixUp(a, index);  
} 

（2）刪除代碼實現(xiàn)

按照堆刪除的說明，堆中每次都只能刪除第0個數據。為了便于重建堆，實際的操作是將數組最后一個數據與根節(jié)點交換，然后再從根節(jié)點開始進行一次從上向下的調整。

調整時先在左右兒子節(jié)點中找最小的，如果父節(jié)點不大于這個最小的子節(jié)點說明不需要調整了，反之將最小的子節(jié)點換到父節(jié)點的位置。此時父節(jié)點實際上并不需要換到最小子節(jié)點的位置，因為這不是父節(jié)點的最終位置。但邏輯上父節(jié)點替換了最小的子節(jié)點，然后再考慮父節(jié)點對后面的節(jié)點的影響。堆元素的刪除導致的堆調整，其整個過程就是將根節(jié)點進行“下沉”處理。下面給出代碼：

// a為數組，len為節(jié)點總數；從index節(jié)點開始調整，index從0開始計算index其子節(jié)點為 2*index+1, 2*index+2；len/2-1為最后一個非葉子節(jié)點 
void minHeapFixDown(int a[],int len,int index) {
	if(index>(len/2-1))//index為葉子節(jié)點不用調整
		return;
	int tmp=a[index];
	lastIndex=index;
	while(index<=len/2-1)        //當下沉到葉子節(jié)點時，就不用調整了
	{ 
		// 如果左子節(jié)點小于待調整節(jié)點
		if(a[2*index+1]<tmp) {
			lastIndex = 2*index+1;
		}
		//如果存在右子節(jié)點且小于左子節(jié)點和待調整節(jié)點
		if(2*index+2<len && a[2*index+2]<a[2*index+1]&& a[2*index+2]<tmp) {
			lastIndex=2*index+2;
		}
		//如果左右子節(jié)點有一個小于待調整節(jié)點，選擇最小子節(jié)點進行上浮
		if(lastIndex!=index) {
			a[index]=a[lastIndex];
			index=lastIndex;
		} else break;             //否則待調整節(jié)點不用下沉調整
	}
	a[lastIndex]=tmp;           //將待調整節(jié)點放到最后的位置
}

根據堆刪除的下沉思想，可以有不同版本的代碼實現(xiàn)，以上是和孫凜同學一起討論出的一個版本，在這里感謝他的參與，讀者可另行給出。個人體會，這里建議大家根據對堆調整過程的理解，寫出自己的代碼，切勿看示例代碼去理解算法，而是理解算法思想寫出代碼，否則很快就會忘記。

（3）建堆

有了堆的插入和刪除后，再考慮下如何對一個數據進行堆化操作。要一個一個的從數組中取出數據來建立堆吧，不用！先看一個數組，如下圖：

很明顯，對葉子節(jié)點來說，可以認為它已經是一個合法的堆了即20，60， 65， 4， 49都分別是一個合法的堆。只要從A[4]=50開始向下調整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分別作一次向下調整操作就可以了。下圖展示了這些步驟：

寫出堆化數組的代碼：

// 建立最小堆
// a:數組，n：數組長度
void makeMinHeap(int a[], int n) {
    for (int i = n/2-1; i >= 0; i--)  
        minHeapFixDown(a, i, n);  
}  

2.2.4 堆的具體應用——堆排序

堆排序（Heapsort）是堆的一個經典應用，有了上面對堆的了解，不難實現(xiàn)堆排序。由于堆也是用數組來存儲的，故對數組進行堆化后，第一次將A[0]與A[n - 1]交換，再對A[0…n-2]重新恢復堆。第二次將A[0]與A[n – 2]交換，再對A[0…n - 3]重新恢復堆，重復這樣的操作直到A[0]與A[1]交換。由于每次都是將最小的數據并入到后面的有序區(qū)間，故操作完成后整個數組就有序了。有點類似于直接選擇排序。

因此，完成堆排序并沒有用到前面說明的插入操作，只用到了建堆和節(jié)點向下調整的操作，堆排序的操作如下：

// array:待排序數組，len：數組長度
void heapSort(int array[],int len) {
	// 建堆
	makeMinHeap(array,len); 
	// 最后一個葉子節(jié)點和根節(jié)點交換，并進行堆調整，交換次數為len-1次
	for(int i=len-1;i>0;--i) {
		//最后一個葉子節(jié)點交換
		array[i]=array[i]+array[0];
		array[0]=array[i]-array[0];
		array[i]=array[i]-array[0];
        // 堆調整
		minHeapFixDown(array, 0, len-i-1);  
	}
}

（1）穩(wěn)定性。堆排序是不穩(wěn)定排序。

（2）堆排序性能分析。由于每次重新恢復堆的時間復雜度為O(logN)，共N-1次堆調整操作，再加上前面建立堆時N/2次向下調整，每次調整時間復雜度也為O(logN)。兩次操作時間復雜度相加還是O(NlogN)，故堆排序的時間復雜度為O(NlogN)。

最壞情況：如果待排序數組是有序的，仍然需要O(NlogN)復雜度的比較操作，只是少了移動的操作；

最好情況：如果待排序數組是逆序的，不僅需要O(NlogN)復雜度的比較操作，而且需要O(NlogN)復雜度的交換操作，總的時間復雜度還是O(NlogN)。

因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般優(yōu)于快速排序的重要一點是數據的初始分布情況對堆排序的效率沒有大的影響。

總結

本篇文章的內容就到這了，希望大家可以喜歡，也希望大家可以多多關注腳本之家的其他精彩內容！

最新評論