目錄

一，樹概念及結構

二，二叉樹概念及結構

特殊的二叉樹：

二叉樹的性質：

二叉樹的存盤結構：

三，二叉樹的順序結構及實作

二叉樹的順序結構：

堆的概念及結構：

堆的實作：

建堆：

堆向下調整演算法：

堆排序：

建堆的時間復雜度：

四，堆的實作：

堆的初始化

堆的列印

堆的銷毀

堆的插入

判空

洗掉堆頂的資料

獲取堆頂的資料，也就是最大值，并計算堆的元素個數

?

具體代碼：Gitee堆的實作

五，TopK問題

一，樹概念及結構

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

特點：
·有一個特殊的結點，稱為根結點，根節點沒有前驅結點，
·除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，因此，樹是遞回定義的，

二，二叉樹概念及結構

特殊的二叉樹：

1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹，
2. 完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，

完全二叉樹的節點個數范圍最多：2^k-1，最少:2^(k-1)-1+1 = 2^(k-1)

二叉樹的性質：

1. 若規定根節點的層數為1，則一棵非空二叉樹的第 i 層上最多有 2^(i-1)個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h-1
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為n0 , 度為2的分支結點個數為n2,則有 n0＝n2＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度,h=log2(n+1)

二叉樹的存盤結構：

二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，

這里目前所學的知識有限，本文只列出了順序結構：

順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

物理公式：下標表示樹中父子關系公式：

leftchild = parent*2+1

rightchild = parent*2+2

parent = (child-1)/2

三，二叉樹的順序結構及實作

二叉樹的順序結構：

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，

堆的概念及結構：

小根堆（根是最小值）：樹中所有父親都小于等于孩子

大根堆（根是最大值）：樹中所有父親都大于等于孩子

堆的實作：

建堆：

給了一個隨機的陣列，我們可以把這個陣列看做完全二叉樹，思考如果變成堆（大堆/小堆）

思考：如何將其變為大堆/小堆?

堆向下調整演算法：

特殊資料的特征：根下面左右子樹都是小堆/大堆

堆排序：

代碼實作：

void swap(int* px,int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
//向下調整演算法（建大堆）
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;//指向的是左孩子
	while (child < n)
	{
		//選出小的孩子中大的那個
		if (child+1 < n && a[child+1] > a[child])
		{
			child++;
		}
		//如果大的孩子比父親大，則交換，繼續往下調整
		//如果大的孩子比父親小，則結束調整
		if (a[child] > a[parent])
		{
			swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序——高效率
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a,n,i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a,end,0);
		end--;
	}
}
int main()
{
	int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	HeapSort(a,sizeof(a)/sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf(" %d",a[i]);
	}
	return 0;
}

建堆的時間復雜度：

注意點：

第一點：倒著走，第一個非葉子節點的子樹開始調，它是最后一個節點的父親

第二點：堆排序，將最大的數和最后一個數交換，再向下調整，時間復雜度O(N*logN)

四，堆的實作：

堆的初始化

先初始化為陣列a，然后在建堆（這里建大堆）

void HeapInit(Hp* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType)*n);

	//建堆
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
	php->size = n;
	php->capacity = n;
}

初始化除錯：

堆的列印

void HeapPrint(Hp*php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf(" %d", php->a[i]);
	}
	printf("\n");
}

堆的銷毀

void HeapDestroy(Hp* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

堆的插入

插入x，首先要先判斷是不是滿了，滿了就需要擴容！

其次，還要繼續保持其實堆，這里采用向上調整法！

向上調整：

//向上調整演算法：
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(Hp* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType*tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (php->a == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		php->capacity = (php->capacity) * 2;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

判空

bool HeapEmpty(Hp* php)
{
	assert(php);
	return php->size == 0;
}

洗掉堆頂的資料

這里洗掉堆頂的資料，要先判空，然后洗掉后還繼續保持其是大堆

//洗掉堆頂即根節點的資料，洗掉后保持其繼續是堆
void HeapPop(Hp* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size,0);
}

獲取堆頂的資料，也就是最大值，并計算堆的元素個數

//獲取堆頂的資料，也就是最值
HPDataType HeapTop(Hp* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
int HeapSize(Hp* php)
{
	assert(php);
	return php->size;
}

運行測驗：

具體代碼：Gitee堆的實作

五，TopK問題

思路：

void PrintTopK(int*a, int n, int k)
{
	Hp hp;
	HeapInit(&hp,a,k);
	for (int i = k; i < n; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp,a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}

思考：n個數的陣列a——如何用向上調整建堆？

for (int i = 1; i < n; i++)
{
	adjustup(a,i);
}