這篇博客會完整的對于樹，堆的概念，堆的應用（topk問題，堆排序）進行深度的剖析

tree.c

`#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>





//如何表示一個樹呢（代碼實作如何定義結構）
//法1.假設說明了樹的度是N（最大是這么多）
 
struct treenode
{
	int data;
	struct treenode*subs[N];//這個陣列是一個指標陣列，里面存的都是指標，但是有缺陷，問題在于
	//1.可能會存在不少空間的浪費，如假設只有一個樹的度是8，其余的都是0，1，2……浪費了很多空間
	//萬一沒有給我們樹的度為多少呢，

};


//法2；
//假設我們已經定義了一個順序表seqlist出來了，資料型別是
//typedef struct treenode* seqdata
//這個順序表里面存的是節點的指標

//struct treenode
//{
//	int data;
//	seqlist s;//
//};


//法3.結構陣列村粗

//struct treenode
//{
//	int parenti;
//	int data;
//
//};


//上面的方式各有優缺點，表示樹結構的最優方法，  使用左孩子右兄弟表示法

typedef int datatype;

struct node
{
	struct node*firstchild;//第一個孩子節點，    永遠指向第一個孩子
	struct node*pnextbrother;//指向下一個兄弟節點  指向孩子右邊的兄弟
	datatype data;   //節點中的資料域
};


//二叉樹
//不學習他的增刪查改，沒有意義
//而是去控制一下他的結構（高度，深度）
//作用是搜索二叉樹：用來進行查找，-》平衡搜索二叉樹，（avl樹和紅黑樹，b樹）（這些結構才會去學習他的增刪查改）

heap.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>



//堆是一個完全二叉樹
//我們已經推導了公式，已知父親，左為父*2+1，右為父*2+2
//已知孩子，父親為（子-1）/2




typedef int hpdata;
typedef struct heap
{
	//物理結構就是一個順序表
	hpdata *a;
	int size;
	int capacity;
}heap;


//初始化
void heapinit(heap* hp);


// 銷毀
void heapdestroy(heap* hp);

//插入
void heappush(heap *hp, hpdata x);

//洗掉

void heappop(heap*hp);


void adjustup(hpdata *a, int n, int child);

void heapprint(heap*hp);


//判空
bool heapempty(heap*hp);


int heapsize(heap*hp);

//
void swap(hpdata*x, hpdata*y);

//向下調
void adjustdown(int *a, int size, int parent);

heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"


//初始化
void heapinit(heap* hp)
{
	assert(hp);
	hp->capacity =hp->size= 0;
	hp->a = NULL;
}


// 銷毀
void heapdestroy(heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

//向上調整
void adjustup(hpdata *a, int n, int child)//a就是這陣列，n就這個陣列右多大
{
	assert(a);
	int parent = (child - 1) / 2;
	//while(parent>=0)
	while (child >0)//調到根
	{
		if (a[child] > a[parent])//大于就交換
		{
			//交換
			hpdata tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;//小于就停止
		}
	}

}







//插入
//假設是大堆
void heappush(heap *hp, hpdata x)
{
	assert(hp);
	//滿了就要先增容
	if (hp->size == hp->capacity)
	{
		size_t newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		hpdata *tmp = (hpdata*)realloc(hp->a, sizeof(hpdata)*newcapcity);
		if (tmp != NULL)
		{
			hp->a = tmp;
			hp->capacity = newcapcity;
		}
		else
		{
			perror("realloc");
			return;
		}
	}
	hp->a[hp->size] = x;
	hp->size++;
	adjustup(hp->a, hp->size, hp->size-1);



}

void heapprint(heap*hp)
{
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
}


```c

bool heapempty(heap*hp)
{
	assert(hp);
	return hp->size == 0;//為0就是空的，不為0就不是空的


}

int heapsize(heap*hp)
{
	assert(hp);
	return hp->size;
}
//向上調的時間復雜度是
//
//向上調高度次
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;
		}
	}
}

//洗掉
//再堆里面洗掉不是隨便任意洗掉什么位置都可以
//而是洗掉堆頂的資料（根），意義是調整堆，找到次小的值（小堆）
//向下調整，把他調整成堆，跟左右孩子中小的那個交換
//結束條件
//1.父親<=小的那個孩子，則停止
//2.調整到葉子（當父親走到葉子就停止，葉子是沒有左孩子，左孩子下標超出陣列范圍就不存在）
void heappop(heap*hp)
{
	assert(hp);
	assert(!heapempty(hp));//空了就別洗掉了
	//先把堆頂和底部刪掉
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;//刪掉了
	//交換之后，向下調整，保證不破壞堆,從0開始向下調
	adjustdown(hp->a, hp->size, 0);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"heap.h"


int main()
{
	int a[] = { 70,56,30,25,15,10,75 };//用陣列去給hp值
	heap HP;//定義一個堆
	heapinit(&HP);
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		heappush(&HP, a[i]);
}
	heapprint(&HP);

	return 0;
}

堆的應用

1.topk問題

topk問題
（就是再n個數里面找到最大的前k個，或者最小的前k個）
1.排序：我們最常見的想法就是把所有資料排一遍，然后找到其中最大的k個，但是這樣假如說n非常非常大，而k卻遠小于n，那么就相當于殺雞用牛刀，這種方法的最有的時間復雜度是O（n*logn）
2.我們最優的方法是是先取前k個建立一個小堆，建立小堆之后，頂部的一定是最小的，隨后，n-k個入堆，與頂比較，如果比頂部的大，就交換，到最后剩下的 那k個一定就是符合要求的

// 在N個數找出最大的前K個  or  在N個數找出最小的前K個
void PrintTopK(int* a, int n, int k)
{
	heap hp;
	heapinit(&hp);
	// 創建一個K個數的小堆
	for (int i = 0; i < k; ++i)
	{
		heappush(&hp, a[i]);//一個一個入堆
	}

	// 剩下的N-K個數跟堆頂的資料比較，比他大，就替換他進堆
	for (int i = k; i < n; ++i)
	{
		if (a[i] > heaptop(&hp))//比較，大的就入堆
		{
			heappop(&hp);//把頂補的刪掉，
			heappush(&hp, a[i]);//大的入堆
			//hp.a[0] = a[i];//把頂部的換成現在大的
			//adjustdown(hp.a, hp.size, 0);//向下調整
		}
	}

	heapprint(&hp);

	heapdestroy(&hp);
}

void TestTopk()
{
	int n = 1000000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	// 再去設定10個比100w大的數
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[5355] = 1000000 + 3;
	a[51] = 1000000 + 4;
	a[15] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}
int main()
{
TestTopk();
return 0;
}

2.堆排序

//堆排序
//首先先建堆，再應用堆進行排序
//升序就建大堆，降序就建小堆

void HeapSort(int* a, int n)
{

	//法1.
	// 直接把a構建成堆，直接控制a陣列，升序，吧
	//把a構建成小堆
	//第一個數先看做堆，后面的資料依次加入堆，然后向上調整，構建堆,調到根就結束了，保證他還是堆
//	if (n <= 1)//第一個就看成堆
//	{
//		return;
//}
	//for (int i = 1; i < n; i++)//后面的數加入進去
	//{
	//	AdjustUp(a,i);
	//}

	//法2；
	//向下調整也可以，保證左子樹和右子樹都小堆，倒著走最后一個子樹進行調整
	//葉子所在的子樹不需要調，所以倒著走的第一個非子節點的子樹，就是最后一個節點的父親，調完之后--，直到根 
	//前面的調整為后面做了鋪墊，前面調整完之后一定是一個堆
	for (int i = (n - 1-1) / 2; i >= 0; i--)//最后一個位置是n-1，
	{
		AdjustDown(a, n, i);
	}

	//排升序建小堆的分析：
	//1.選出了最小的數放到第一個位置，如何選出次小的位置，只能從第二個位置開始，剩下的數看成一個堆，但是這樣的話所有的關系都亂了，只能重新建堆才可以選出次小的堆

	//我們建大堆，最大的數選出來，
	//最大的數放最后一個位置，交換
	//如何選出此校的 數，1.把最后一個數不看做堆里面的了，向下調整就可以選出次小的數，依次內推在重復上面程序，，原本有n個數，現在傳n-1個數，就不把他當做堆里面的了
	
	for (int end = n - 1; end > 0; end--)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);//向下調整，到根部
	}

}