資料結構基礎——堆的概念、結構及應用

目錄

1. 堆的概念
2. 堆這種資料結構的代碼實作
3. 堆在排序演算法上的應用

1.堆的概念

堆就是以二叉樹的順序存盤方式來存盤元素，同時又要滿足父親結點存盤資料都要大于兒子結點存盤資料（也可以是父親結點資料都要小于兒子結點資料）的一種資料結構，堆只有兩種即大堆和小堆，大堆就是父親結點資料大于兒子結點資料，小堆則反之，

堆的性質：
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，

用圖畫展示就如下圖所示：

2.堆這種資料結構的代碼實作

了解了堆的概念之后，我們要實際寫出一個堆來，先寫個小堆為例，
物理結構是用一個陣列來存盤資料，先定義一個動態增長的陣列來，

typedef int Datatype;
typedef struct                                          
{                
	Datatype* a;
	int size;
	int capacity;
}heap;
 //這就是堆的基本形式了，然后再按照完全二叉數的邏輯形式插入資料

在測驗的源檔案中創建一個堆

heap hp;    //之后就可以寫各種堆的功能函式來操作堆了，都是通過傳堆的地址過去來操作的

//在頭檔案中就先宣告跟堆有關的各種介面函式                       
void heapinit(heap* hp);   //堆的初始化
void heapdestroy(heap* hp); //堆的銷毀
void heappush(heap* hp, Datatype x);  //資料進堆
void heappop(heap* hp);   //資料出堆
void heapadjustdown(int* a, int n, int x);//向下調整
void heapadjustup(int* a, int n, int x); //向上調整
void swap(int* a, int* b);   //交換兩個數值
void print(heap* hp);   //列印堆的資料
bool heapEmpty(heap* hp); //判斷堆是否時空堆
int heapSize(heap* hp);  //計算堆的資料元素個數
Datatype heaptop(heap* hp); //獲得堆頂的資料

然后在另一個源檔案中定義這些函式，并加以詳細說明，

void heapinit(heap* hp)
{
   assert(hp);
	hp->a = NULL;  //堆的初始化，此時堆中沒有資料                
	hp->capacity = hp->size = 0;
}

//往堆中加入資料，物理結構上是不斷地在陣列尾部加入資料，但加入資料后就要調整資料維持一個小堆或大堆的邏輯結構,要有一個向上調整的函式，如下圖所示

void heappush(heap* hp, Datatype x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = (hp->capacity == 0) ? 4 : 2 * hp->capacity;
		Datatype* tem = (Datatype*)realloc(hp->a, newcapacity * sizeof(Datatype));
		if (tem == NULL)   //這里就是動態陣列的常規檢查容量問題
		{
			printf("realloc failed\n");
			exit(-1);
		}
		hp->a = tem;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	heapadjustup(hp->a, hp->size, hp->size - 1);
}
void heapadjustup(int* a, int n, int child)
{    //向上調整的函式
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])               //大堆向上調整，用大于號方便識別  小堆就用小于號
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

另一個主要的函式是堆的洗掉資料的函式，規定堆只能從根節點洗掉資料，把堆尾部的資料與根節點的資料交換，然后洗掉被換到堆尾部那個原先在根節點的資料，讓付訓到根結點的資料向下調整維持堆原先的大堆或小堆結構，

void heappop(heap* hp)
{
	assert(hp);
	if (heapEmpty(hp))    //判斷是否還有資料可以洗掉
	{
		printf("沒有資料可刪\n");
		return;
	}
	swap(&hp->a[0], &hp->a[hp->size - 1]);   //交換根結點和最后一個葉節點資料
	hp->size--;
	heapadjustdown(hp->a, hp->size, 0);  //向下調整函式
}

向下調整就跟向上調整有區別了，從根結點開始向下可能有不同的路徑，我們要維持住小堆則最小的數在堆頂，大堆則最大的數在堆頂，具體看下圖所示

//向下調整函式的實作
void heapadjustdown(int* a, int n, int parent)
{
	int  child = 2 * parent + 1;
	while (child < n)    //判斷有沒有到葉子結點
	{
		if (child + 1 < n && a[child + 1] < a[child])   //大堆向下調整，用大于號方便識別  小堆就用小于號
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			swap(a + parent, a + child);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

后面其它函式的實作

void swap(int* a, int* b)   //交換兩個位置的資料
{
	int tem = *a;
	*a = *b;
	*b = tem;
}
void print(heap* hp)    //在螢屏上列印堆的資料
{
	assert(hp);
	assert(hp->a);
	for (int i = 0; i < hp->size; i++)
		printf("%d ", hp->a[i]);
	printf("\n");
}
bool heapEmpty(heap* hp)    //判斷堆是否為空，空就回傳真，否則回傳假
{
	assert(hp);
	return hp->size == 0;
}
int heapSize(heap* hp)   //回傳堆的資料個數
{
	assert(hp);
	return hp->size;
}
Datatype heaptop(heap* hp)   /獲得堆頂的資料
{  
	assert(hp);
	assert(!heapEmpty(hp));
	return hp->a[0];
}
void heapdestroy(heap* hp)   //最紅銷毀堆
{
	assert(hp);
	assert(hp->a);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

3.堆在排序演算法上的應用

用堆這種資料結構來找一組資料中最大的或者最小的幾個資料是一種比較高效的演算法，小堆就是比較大的資料都在堆的下面，如果要找出N個數中最大的K個數，我們可以先用N個數中的K個數建一個小堆，最小的數在堆頂，拿其余N-K個數依次與堆頂資料比較，大于堆頂資料，就拿它更新堆頂資料，在向下調整，比較完這N-K個數后，堆中的K個數就是這N個數中最大的K個數，同理在大堆中最大的數在堆頂，較小的數在堆下面，以同樣的規律，比較資料，如果小于堆頂資料就更新堆頂資料，最后留在堆中的K個數就是N個數中最小的資料，
這里來找一下N個數中最大的K個數，

void printTok(int* a, int n, int k)；//找最大的K個數的函式宣告
void testTok()     //找出N個數中最大的K個數的函式測驗  資料的準備
{
 int N = 10000, k = 10;   
 int* a = (int*)malloc(sizeof(int) * N);
 if (a == NULL)
 {
 	printf("malloc fail\n");
 	exit(-1);
 }
 srand((size_t)time(0));
 for (int i = 0; i < N; i++)
 {
 	a[i] = rand() % 10000;
 }
 a[24] = 10000 + 5;  //事先準備10個最大的數，測驗能不能在10000個數中找出它們
 a[56] = 10000 + 7;
 a[78] = 10000 + 6;
 a[5] = 10000 + 12;
 a[68] = 10000 + 9;
 a[355] = 10000 + 15;
 a[789] = 10000 + 1;
 a[865] = 10000 + 8;
 a[7900] = 10000 + 4;
 a[5846] = 10000 + 3;
 printTok(a, N, 10);
 free(a);
}
void printTok(int* a, int n, int k)   //找最大的K個數的函式實作
{
 int i;
 heap hp;
 heapinit(&hp);
 for (i = 0; i < k; i++)
 {
 	heappush(&hp, a[i]);
 }
 for (i = k; i < n; i++)
 {
 	if (a[i] > heaptop(&hp))
 	{
 		hp.a[0] = a[i];
 		heapadjustdown(hp.a, hp.size, 0);
 	}
 }
 print(&hp);
 heapdestroy(&hp);
}

最后代碼沒問題的話，效果如下圖