• 堆--完全二叉树

    目录

    前言🤠

    在介绍完普通二叉树之后，接下来在介绍一种特殊二叉树，叫做完全二叉树，也就是堆；而堆就有着堆排序以及TopK问题等，在上一篇博客我也在尽量规避这一较为特殊的二叉树，而在这篇博客就可以将其进行详细介绍！
    在这里插入图片描述

    1.完全二叉树🎶

    1.1概念👾

    完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

    在这里插入图片描述

    也就是说，第K层从左到右依次存在结点的树叫做完全二叉树，对于上述图片可以得知满二叉树是完全二叉树，但是完全二叉树不一定是满二叉树；

    关于完全二叉树在之前博客介绍过，在此只是大致提起，不清楚的可以翻看前面博客！

    1.2判断是否为完全二叉树👾

    //利用层序遍历的思路判断是否为完全二叉树
bool BinaryTreeComplete(TreeNode* root)
{
	Queue qe;
	InitQueue(&qe);
	if(root)
	   PushQueue(&qe, root);
	
	//
	while (!QueueEmpty(&qe))
	{
		TreeNode* front = QueueFrontData(&qe);
		PopQueue(&qe);

		if (front == NULL)
		{
			break;
		}
		PushQueue(&qe, front->left);
		PushQueue(&qe, front->right);
	}

	//碰到NULL之后后边不能存在非NULL结点
	while (!QueueEmpty(&qe))
	{
		TreeNode* front = QueueFrontData(&qe);
		PopQueue(&qe);
		if (front != NULL)
		{
			return false;
		}
	}
	DestoryQueue(&qe);
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    利用层序遍历来判断一棵树是否为完全二叉树，对层序遍历不清楚的可以翻看上一篇博客：层序遍历；

    对二叉树所有的结点如同层序遍历一样，一层一层进行访问，将其左右孩子依次写入队列当中，当碰见NULL时退出！

    为什么我上述代码中设置成碰见NULL退出呢？
    在这里插入图片描述

    思路与层序遍历一致，在每次访问时，如果其左右子树不存在时会给队列中读入NULL，当碰见NULL后，如果该树是完全二叉树的话，那么NULL后边的结点应该全是NULL，否则就不是完全二叉树，原理可以参考上图！

    2.堆🎶

    2.1顺序存储👾

    在之前博客，我提到二叉树可以使用顺序存储也可以使用链式存储，而顺序存储就是针对完全二叉树的；

    为什么这么说呢？

    在这里插入图片描述
    如图所示，原因如上，非完全二叉树利用顺序存储的话，会造成大量空间的浪费！

    2.2堆👾

    概念：

    由概念可知，堆是分为大根堆和小根堆的，而如何进行区分呢？也就是根节点是整棵树最小的结点时为为小根堆；反之，则为大根堆

    在这里插入图片描述
    上述推论十分重要，在后续代码实现会用到！

    2.3堆的性质👾

    • 堆中的某个结点的值总是不大于或者不小于其父节点的值；

    • 堆总是完全二叉树

    大根堆：
    在这里插入图片描述
    小根堆：
    在这里插入图片描述

    3.堆的相关操作🎶

    ❗❗❗在堆的插入删除中都实现操作的是小根堆❗❗❗

    因为堆是顺序存储，所以其定义与顺序表一致：

    typedef int HeapDataTypde;
typedef struct Heap
{
	HeapDataTypde* arr;
	int size;
	int capacity;
}Heap;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.1初始化👾

    //初始化
void HeapInit(Heap* hp)
{
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.2堆的插入👾

    堆的插入与其他顺序结构插入时不同的，需要保证插入后堆仍旧为大根堆或者小根堆，因此我们在插入的过程中，就可以实现堆的创建了！

    代码如下：

    //交换
void Swap(HeapDataTypde* x, HeapDataTypde* y)
{
	HeapDataTypde temp = *x;
	*x = *y;
	*y = temp;
}
//插入
void CheckCapacity(Heap* hp)
{
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity * 2);
		int* temp = (int*)realloc(hp->arr, newcapacity * sizeof(int));
		if (temp == NULL)
		{
			perror("realloc fail\n");
			return;
		}
		hp->arr = temp;
		hp->capacity = newcapacity;
	}
}

//向上调整(小堆)
void HeapAdjustUp(HeapDataTypde* arr, int child)
{
	int parent = (child - 1) / 2;
	
	//当child==0时，此时已经在堆顶了
	while (child>0)
	{
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(Heap* hp,HeapDataTypde x)
{
	assert(hp);
	CheckCapacity(hp);
	hp->arr[hp->size] = x;
	hp->size++;
	HeapAdjustUp(hp->arr, hp->size - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    扩容机制与顺序表一致，在此就不进行赘述了，主要对向上调整进行分析，上述代码时模拟实现小根堆；
    在这里插入图片描述

    在整个代码中，因为插入元素后不能保证当前堆是否仍旧为一个大根堆或者小根堆，所以需要进行向上调整；根据推论公式，我们可以得出其父节点的位置，然后与其父节点进行比较，如果父节点大于插入的结点，则进行交换；重复这个过程，直到堆为大根堆或者小根堆即可；当条件不满足时，break跳出即可；

    3.3堆的删除(删除堆顶元素)👾

    //向下调整(调整为小堆)
void HeapAdjustDown(HeapDataTypde* arr, int parent, int n)
{
	int minchild = parent * 2 + 1;//假设左孩子最小
	//保证左孩子不越界
	while (minchild<n)
	{
	    //保证右孩子不越界
		if (arr[minchild] > arr[minchild + 1] && minchild + 1 < n)
		{
			minchild++;
		}
		if (arr[parent] > arr[minchild])
		{
			Swap(&arr[parent], &arr[minchild]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//弹出(堆顶位置的元素)
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
	hp->size--;
	HeapAdjustDown(hp->arr, 0, hp->size);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    在这里插入图片描述
    关于堆得删除的思路如上图所示，会首先将堆顶元素与最后一个元素互换，然后对size–进行删除；而删除后堆顶的元素是不一定满足大堆或者小堆的，因此堆顶就需要进行向下调整；

    向下调整算法的分析：有推论公式可以假定左孩子为其两个孩子中较小得哪一个，因此需要进行比较，将根节点的左右孩子进行比较选出较小得一个，然后与根节点进行比较，如果根节点大于较小得哪一个孩子，则将根节点向下进行调整即可，重复这个过程，最后就可以得到小根堆了！

    3.4其他操作👾

    //判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

//堆顶元素
HeapDataTypde HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->arr[0];
}

//堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

//销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->arr);
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    3.5拓展👾

    在插入和删除当中，模拟实现了小根堆，那么关于大根堆只需要改变其相关的判断条件即可；

    1️⃣向上调整(大堆)：

    if (arr[parent] < arr[child])

    2️⃣向下调整(大堆)

    if (arr[minchild] < arr[minchild + 1] && minchild + 1 < n)
    if (arr[parent] < arr[minchild])

    需要注意的是，在进行插入删除时，向上调整以及向下调整所操作的对象必须一致，换句话说就是操作对象都为大堆或者都为小堆！

    4.堆的创建🎶

    在给定一数组的情况下，如何去将数组创建成大根堆或者小根堆呢？

    在上面我介绍了向上调整算法和向下调整算法，其就是比较父与子的大小关系，因此利用向上调整和向下调整就可以实现堆的创建了！

    4.1向上调整👾

    int arr[] = { 65,100,60,32,50,90 };
for (int i = 1; i < size; i++)
{
	HeapAdjustUp(arr, i);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    而向上调整的时间复杂度为log₂N，所以整体使用向上调整建堆的时间复杂度为N*log₂N;

    4.2向下调整👾

    int arr[] = { 65,100,60,32,50,90 };
for (int i = (size - 1 - 1) / 2; i >= 0; --i)
{
	HeapAdjustDown(arr, i, size);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    向下调整从第一个非叶子结点开始进行，也就是将第一个非叶子结点传入，对该节点与其子节点进行调整；重复这个过程就可以完成建堆。

    在这里插入图片描述

    那么向下调整建堆的时间复杂度为多少呢？

    在这里插入图片描述

    上述是数学的等差数列的应用，而向下建堆的时间复杂度为log₂N，而对于满二叉树而言，当高度为h层时，其节点数为2^h-1，设结点数为n，而h可以表示为log₂(N+1),所以T(N)如上图所示，而将log₂(N+1)省略，所以向下调整建堆的效率是高于向上建堆的效率的！

    关于向上调整和向下调整算法在前面已经介绍过了，所以在建堆时我并没有着重介绍其内容，可以拷贝代码进行调试，从而观察理解！

    5.堆排序🎶

    在经过上述的向上调整和向下调整之后，利用其可以完成建堆的操作；而在堆排序中也是可以利用其完成的。

    5.1升序👾

    在升序中，需要建成一个大堆，然后利用Swap函数将根节点与最后一个结点进行交换；然后对剩下size-i个结点进行调整，重新调整成一个大堆即可！

    for (int i = (size - 1 - 1) / 2; i >= 0; --i)
{
	BigHeapAdjustDown(arr, i, size);
}
for (int i = 0; i < size; i++)
{
	Swap(&arr[0], &arr[size - 1 - i]);
	BigHeapAdjustDown(arr, 0, size - 1 - i);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    分析：首先先进行调整，将已知数组调整成一个大堆；然后在第二个for循环中，完成交换操作，在对剩下的数进行调整，重新建堆，重复上述过程就可以完成升序的操作！

    5.2降序👾

    降序与升序刚好相反，首先需要建成一个小堆；然后依次交换，将根节点依次放到后边；然后重现调整建堆！

    for (int i = (size - 1 - 1) / 2; i >= 0; --i)
{
	SmallHeapAdjustDown(arr, i, size);
}
for (int i = 0; i < size; i++)
{
	Swap(&arr[0], &arr[size - 1 - i]);
	SmallHeapAdjustDown(arr, 0, size - 1 - i);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    分析：原理与升序相反，在此就不赘述了！

    关于对排序的升序和降序的代码如下：

    //排序----时间复杂度为O（N*logN）
void HeapSort(int*arr,int size)
{
	//升序---建大堆
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		BigHeapAdjustDown(arr, i, size);
	}
	for (int i = 0; i < size; i++)
	{
		Swap(&arr[0], &arr[size - 1 - i]);
		BigHeapAdjustDown(arr, 0, size - 1 - i);
	}


	//降序---(建小堆)
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		SmallHeapAdjustDown(arr, i, size);
	}
	for (int i = 0; i < size; i++)
	{
		Swap(&arr[0], &arr[size - 1 - i]);
		SmallHeapAdjustDown(arr, 0, size - 1 - i);
	}

	//打印
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    6.TopK问题🎶

    在存在N个数，需要找到N个数中最大的K个数或者最小的K个数，形如这样的一种情况就被叫做TopK问题。

    一、可以建成大堆或者小堆利用上述堆的删除从而不断的进行调整即可，而当数据量很大时，这种办法就不能够解决问题了！

    二、建堆
    1.先在数据集合中拿出K个数做堆

    • (1)求K个最大元素的值，需要建成小堆
    • (2)求K个最小元素的值，需要建成大堆
    2.对剩下N-K个元素与堆顶的元素进行比较；如果是取最大的K个元素，就与小堆的堆顶元素进行比较，如果比堆顶元素大则对堆顶进行重新赋值，然后重新建堆。反之，则与大堆的堆顶元素比较，对堆顶进行重新赋值，然后重新建堆。

    思路如上，而该如何实现呢？下面我结合文件操作生成随机数从而验证并实现解决TopK问题！

    6.1生成随机数保存至文件中👾

    //创造文件
void CreateFile(const char* filename, int N)
{
	FILE* fout = fopen(filename, "w");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	srand(time(0));
	for (int i = 0; i < N; i++)
	{
		fprintf(fout, "%d\n", rand());
	}

	fclose(fout);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    srand是生成随机数的一个函数，生成随机数保存至文件逻辑很简单，在此不进行介绍了，对相关内置函数不熟悉的可以在社区搜索！

    6.2 K个最大数👾

    //取前K个较大得数----建小堆进行比较
void HeapTopBigK(const char* filename, int k)
{
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	//读取前N个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	//建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		SmallHeapAdjustDown(minheap, i, k);
	}

	//交换
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minheap[0])
		{
			minheap[0] = val;
			SmallHeapAdjustDown(minheap, 0, k);
		}
	}

	printf("前K个最大的元素:");
	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	fclose(fout);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    分析：前面提到，要解决K个最大数的问题时，需要先建成一个K个数据的小堆；在建堆之前，需要从之前所生成的文件中读取K个数；完成上述两个操作后，对剩下的N-K数与小堆的堆顶数据元素进行比较，如果比小堆的堆顶的数据都大的话，则将小堆的堆顶数据进行更新，然后重新调整成小堆；重复上述过程即可完成对寻找K个最大的数。

    6.3 K个最小值👾

    //取前K较小得数----建大堆进行比较
void HeapTopSmallK(const char* filename, int k)
{
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* maxheap = (int*)malloc(sizeof(int) * k);
	if (maxheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	//取前K个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &maxheap[i]);
	}
	//做大堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		BigHeapAdjustDown(maxheap, 0, k);
	}
	//比较
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val < maxheap[0])
		{
			maxheap[0] = val;
			BigHeapAdjustDown(maxheap, 0, k);
		}
	}

	printf("前K个最小的元素：");
	for (int i = 0; i < k; i++)
	{
		printf("%d ", maxheap[i]);
	}
	printf("\n");

	fclose(fout);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    分析：思路与上述一致，不过在建堆和判断条件时域上述相反，可结合上面对K个最大值的分析理解K个最小值，在此就不进行赘述了！

    Ending👨‍💻

    关于堆也就是完全二叉树也就介绍完成了，在本次博客中的起始介绍了如何判断完全二叉树；以及介绍了堆排序，这是一种效率很不错的排序，在之如何解决TopK问题；于我认为，最主要的就是向下调整以及向上调整，如果可以很好理解这两种算法，在后续建堆以及排序等内容中就可以很好的去码写堆排序之类的问题了！

    ok,就这样吧🙋‍♂️🙋‍♂️🙋‍♂️
    在这里插入图片描述

  • 相关阅读:
    农民工学CSAPP题目解析-前篇题目解答以及答疑总结
    迭代器失效问题
    vue render里面阻止事件冒泡
    算法基础课
    【ASP.NET Core 基础知识】--最佳实践和进阶主题--设计模式在ASP.NET Core中的应用
    数据结构和算法之排序和查找
    一个简易的makefile模板
    为什么使用前端框架
    我想外包开发一个预约类小程序，大概需要多少钱？
    Java批量修改文件名
  • 原文地址：https://blog.csdn.net/weixin_57248528/article/details/126423636