前言

博主上一小節動圖演示堆講到了通過堆的特性進行堆排序,今天博主將要提到的就是詳細了解堆,以及實作堆操作

堆的結構化

既然我們知道是堆是一種特殊的二叉樹,并且是用順序表進行實作的,那么我們便嘗試著用順序表進行實作堆的高級操作,比如入堆,出堆,初始化等等.

定義堆

既然是用順序表實作堆,那么我們便需要借助順序表,代碼如下:

typedef int HeapDataType;
typedef struct heap      //堆
{
    HeapDataType* num;     //陣列
    int size;
    int capacity;
}heap;

堆的各種操作方法

既然堆是一種資料結構,那么它同樣與其他資料結構一樣,具有增刪改查等功能,所以我們現在先宣告各種方法,后面再一一實作各個方法.

堆的初始化宣告:

//堆初始化主要負責把陣列num中的數字轉移到pheap->num中,然后把pheap->num中的資料轉換為堆的邏輯結構
void HeapInit(heap* pheap,HeapDataType* num,int n);   //n是陣列長度

堆的銷毀

//當此堆不再使用以后就要銷毀空間
void HeapDestroy(heap* pheap);

資料載入堆

//此函式作用是把新資料載入堆,并且還要保持堆的結構不被破壞
void HeapPush(heap* pheap,int n);

洗掉堆頂元素

//此函式作用是為了洗掉堆頂元素并且堆結構不能被破壞,最后還需要回傳所洗掉的元素
HeapDataType HeapPop(heap* pheap);

判斷堆中資料是否為空

bool HeapEmpty(heap* pheap);

獲取堆頂元素

HeapDataType HeapTop(heap* pheap);

獲取堆的大小

int HeapSize(heap* pheap);

此外,沒有看博主上一節文章動圖演示堆排序的小伙伴先看下堆排序哦,下面博主會直接貼出向下調整演算法,不再解釋了哦~~

向下調整演算法:

void AdjustDown(int num[], int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && num[child] < num[child + 1])
		{
			child++;
		}

		if (num[parent] < num[child])
		{
			Swap(&num[parent], &num[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆操作之初始化

堆初始化主要負責把陣列num中的數字轉移到pheap->num中,然后把pheap->num中的資料轉換為堆的邏輯結構

所以涉及的內容為陣列拷貝(挨個賦值也可以),動態空間開辟,向下調整演算法進行建堆

void HeapInit(heap* pheap, HeapDataType* num, int n)
{
	assert(pheap);
	//第一步,開辟空間
	HeapDataType* tmp = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
	if (tmp == NULL)
	{
		printf("空間開辟失敗,抱歉!\n");
		exit(-1);
	}
	pheap->num = num;
	pheap->size = pheap->capacity = n;   //初始化陣列大小和容量

	//第二步,拷貝陣列.
	memcpy(pheap->num, num, sizeof(HeapDataType) * n);

	//第三步,建堆.
	for (int parent = (n - 1 - 1) / 2; parent >= 0; parent--)
	{
		AdjustDown(pheap->num, n, parent);
	}
}

堆操作之銷毀空間

堆銷毀空間很簡單,直接free掉num就行

void HeapDestroy(heap* pheap)
{
	assert(pheap);
	free(pheap->num);
	pheap->num = NULL;
}

堆操作之入堆

該函式的要求是資料必須進入堆,并且不能毀掉堆的特性.大家想想有什么辦法可以解決?

答案是進行向上調整,程序如下圖(以小堆為例子):

觀察上圖,我們發現向上調整的步驟是:

• 資料首先載入最后
• 與其雙親結點進行比較,如果比雙親結點小,就交換其值,一直不斷重疊
• 如果該資料比雙親結點值大,就結束調整;如果當child等于0,就結束調整

所以代碼如下:

void HeapPush(heap* pheap, int n)
{
	assert(pheap);

	//第一步,需要檢查堆空間是否足夠繼續存盤新資料,不足時候句增加空間,這一步很多人總是忽略
	if (pheap->size == pheap->capacity)
	{
		HeapDataType* tmp = (HeapDataType*)realloc(pheap->num, pheap->capacity * 2 * sizeof(HeapDataType));
		if (tmp == NULL)
		{
			printf("空間不足,系統嘗試增容,但是抱歉,增容失敗.\n");
			exit(-1);
		}
		pheap->capacity *= 2;
	}

	//資料入堆
	pheap->num[pheap->size] = n;
	pheap->size++;

	//開始向上調整
	AdjustUp(pheap->num, pheap->size-1);
}

上面我們可以把向上調整寫成一個函式

void AdjustUp(HeapDataType num[], int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)   //主要動的就是child位置,所以child>0
	{
		if (num[child] < num[parent])
		{
			Swap(&num[child], &num[parent]);   //自己寫一個交換函式
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆操作之出堆

該函式的作用是洗掉堆頂元素,并且不能毀壞堆結構,大家想想有什么辦法呢?

答案是,借助堆排序的思想,先把堆頂元素與最后一個元素交換,然后不管最后一個元素,重新進行向下調整.

仍然以小堆為例,看下圖演示:

HeapDataType HeapPop(heap* pheap)
{
	assert(pheap);
	assert(!HeapEmpty(pheap));
	//保存需要洗掉的值
	HeapDataType return_value = pheap->num[0];

	//交換首位
	Swap(&pheap->num[0], &pheap->num[pheap->size - 1]);
	pheap->size--;   //當size減一就代表著已經洗掉了最后一個值.

	//向下調整
	AdjustDown(pheap->num, pheap->size, 0);

	//回傳
	return return_value;
}

堆操作之判空

bool HeapEmpty(heap* pheap)
{
    assert(pheap);
    return pheap->size == 0;
}

堆操作之獲取堆頂

HeapDataType HeapTop(heap* pheap)
{
    assert(pheap);
    assert(!HeapEmpty(pheap));
    return pheap->num[0];
}

堆操作之獲取大小

int HeapSize(heap* pheap)
{
    assert(pheap);
    return pheap->size;
}

堆結構練習:獲取前k個最小或最大元素

題目:

假設有陣列num,其內容的定義如下:

#include <time.h>
int main()
{
    int num[10000] = {0};
	srand(time(NULL));
    for(int i = 0;i<10000;i++)
    {
        num[i] = rand() % 10000;  //保證陣列中每個元素都是小于10000;
    }
    
    for(int i = 0;i<10;i++)
    {
        num[rand() % 10000] = rand()%10 + 10001;  //隨機給陣列賦值10個大于10000的數.
    }
}

要求:寫一個演算法,求出該陣列前10個大于10000的數.

而這我們就可以利用堆的特性,因為堆的最值永遠在堆頂,所以每次獲取洗掉堆頂的元素就行

void  SetNarry(int num[])
{
    srand(time(NULL));
    for (int i = 0; i < 10000; i++)
    {
        num[i] = rand() % 10000;  //保證陣列中每個元素都是小于10000;
    }

    for (int i = 0; i < 10; i++)
    {
        int ret = 0;
        num[ret = rand() % 10000] = rand() % 10 + 10001;  //隨機給陣列賦值10個大于10000的數.
    }
}

int main()
{
    heap hp = { 0 };
    int  num[10000] = { 0 };

    SetNarry(num); //給陣列賦值

    HeapInit(&hp, num,10000); //變成堆,初始化函式里面的向下調整演算法注意修改成大堆演算法哦

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", HeapPop(&hp));
    }
    return 0;
}

測驗:

成功

我們分析下這種演算法的時間復雜度是多少?

建堆時間復雜度為O(N) , 洗掉堆頂時間復雜度復雜為O(k * logN),所以最后時間復雜度為O(N+k * logN).

現在我們對資料升級了,假設有100億個資料,電腦記憶體存不下了,請問該怎樣利用堆特性解決?

這是一道思考題,博主就不贅述了,大家仔細想想哦~~