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

1.1 棧簡介

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

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

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

1.2 堆簡介

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

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

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

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

1.3 堆與棧區(qū)別

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

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

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

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

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

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

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

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

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

2.數(shù)據(jù)結(jié)構(gòu)中的堆與棧

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

2.1 棧簡介

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

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

棧的結(jié)構(gòu)如下圖所示：

棧的基本操作包括初始化、判斷棧是否為空、入棧、出棧以及獲取棧頂元素等。下面以順序棧為例，使用 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("當(dāng)前棧中的元素:\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);
		//打印棧內(nèi)所有元素
		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;
}

運行上面的程序，輸出結(jié)果：

當(dāng)前棧中的元素:

7 5 4

top element is 7

pop top element is 7

2.2 堆簡介

2.2.1 堆的性質(zhì)

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

下面是一個小頂堆示例：

堆的存儲一般都用數(shù)組來存儲堆，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）建立

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

（2）插入

將一個新元素插入到表尾，即數(shù)組末尾時，如果新構(gòu)成的二叉樹不滿足堆的性質(zhì)，需要重新排列元素，下圖演示了插入15時，堆的調(diào)整。

（3）刪除。

堆排序中，刪除一個元素總是發(fā)生在堆頂，因為堆頂?shù)脑厥亲钚〉模ㄐ№敹阎校?。表中最后一個元素用來填補空缺位置，結(jié)果樹被更新以滿足堆條件。

2.2.3 堆操作實現(xiàn)

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

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

// 新加入i節(jié)點,其父節(jié)點為(i-1)/2
// 參數(shù)：a：數(shù)組，i：新插入元素在數(shù)組中的下標  
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;  
}  

因此，插入數(shù)據(jù)到最小堆時：

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

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

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

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

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

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

（3）建堆

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

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

寫出堆化數(shù)組的代碼：

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

2.2.4 堆的具體應(yīng)用——堆排序

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

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

// array:待排序數(shù)組，len：數(shù)組長度
void heapSort(int array[],int len) {
	// 建堆
	makeMinHeap(array,len); 
	// 最后一個葉子節(jié)點和根節(jié)點交換，并進行堆調(diào)整，交換次數(shù)為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];
        // 堆調(diào)整
		minHeapFixDown(array, 0, len-i-1);  
	}
}

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

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

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

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

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

總結(jié)

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

最新評論