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

1.1 棧簡(jiǎn)介

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

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

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

1.2 堆簡(jiǎn)介

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

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

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

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

1.3 堆與棧區(qū)別

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

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

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

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

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

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

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

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

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

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

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

2.1 棧簡(jiǎn)介

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

棧分順序棧和鏈?zhǔn)綏煞N。棧是一種線性結(jié)構(gòu)，所以可以使用數(shù)組或鏈表（單向鏈表、雙向鏈表或循環(huán)鏈表）作為底層數(shù)據(jù)結(jié)構(gòu)。使用數(shù)組實(shí)現(xiàn)的棧叫做順序棧，使用鏈表實(shí)現(xiàn)的棧叫做鏈?zhǔn)綏＃叩膮^(qū)別是順序棧中的元素地址連續(xù)，鏈?zhǔn)綏Ｖ械脑氐刂凡贿B續(xù)。

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

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

#include<stdio.h>
#include<malloc.h>
#define DataType int
#define MAXSIZE 1024
struct SeqStack {
	DataType data[MAXSIZE];
	int top;
};
//棧初始化,成功返回棧對(duì)象指針，失敗返回空指針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;
}

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

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

7 5 4

top element is 7

pop top element is 7

2.2 堆簡(jiǎn)介

2.2.1 堆的性質(zhì)

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

下面是一個(gè)小頂堆示例：

堆的存儲(chǔ)一般都用數(shù)組來(lái)存儲(chǔ)堆，i節(jié)點(diǎn)的父節(jié)點(diǎn)下標(biāo)就為 ( i – 1 ) / 2 (i – 1) / 2 (i–1)/2。它的左右子節(jié)點(diǎn)下標(biāo)分別為 2 ∗ i + 1 2 * i + 1 2∗i+1 和 2 ∗ i + 2 2 * i + 2 2∗i+2。如第0個(gè)節(jié)點(diǎn)左右子節(jié)點(diǎn)下標(biāo)分別為1和2。

2.2.2 堆的基本操作

（1）建立

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

（2）插入

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

（3）刪除。

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

2.2.3 堆操作實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

（3）建堆

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

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

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

// 建立最小堆
// a:數(shù)組，n：數(shù)組長(zhǎng)度
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）是堆的一個(gè)經(jīng)典應(yīng)用，有了上面對(duì)堆的了解，不難實(shí)現(xiàn)堆排序。由于堆也是用數(shù)組來(lái)存儲(chǔ)的，故對(duì)數(shù)組進(jìn)行堆化后，第一次將A[0]與A[n - 1]交換，再對(duì)A[0…n-2]重新恢復(fù)堆。第二次將A[0]與A[n – 2]交換，再對(duì)A[0…n - 3]重新恢復(fù)堆，重復(fù)這樣的操作直到A[0]與A[1]交換。由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個(gè)數(shù)組就有序了。有點(diǎn)類(lèi)似于直接選擇排序。

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

// array:待排序數(shù)組，len：數(shù)組長(zhǎng)度
void heapSort(int array[],int len) {
	// 建堆
	makeMinHeap(array,len); 
	// 最后一個(gè)葉子節(jié)點(diǎn)和根節(jié)點(diǎn)交換，并進(jìn)行堆調(diào)整，交換次數(shù)為len-1次
	for(int i=len-1;i>0;--i) {
		//最后一個(gè)葉子節(jié)點(diǎn)交換
		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ù)堆的時(shí)間復(fù)雜度為O(logN)，共N-1次堆調(diào)整操作，再加上前面建立堆時(shí)N/2次向下調(diào)整，每次調(diào)整時(shí)間復(fù)雜度也為O(logN)。兩次操作時(shí)間復(fù)雜度相加還是O(NlogN)，故堆排序的時(shí)間復(fù)雜度為O(NlogN)。

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

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

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

總結(jié)

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

最新評(píng)論