【数据结构】堆

二叉树

树的概念

树是一种非线性结构，树是递归定义的。

树形结构中子树之间不能有交集

相关概念

子节点，父节点，兄弟节点

叶节点或终结点，节点的度，树的深度，森林

定义方法

左孩子右兄弟表示法

typedef int DataType;
struct TreeNode
{
	struct TreeNode* firstChild1;
	struct TreeNode* pNextBrother;
	DataType data;
};

二叉树的概念和结构

特殊的二叉树

• 满二叉树：

  每一层的节点都达到了最大值，如果有k层。那么最多有2**k-1个节点。

• 完全二叉树

  前k-1层是满的，最后一层从左到右是连续的。高度为h的完全二叉树节点范围是【2^(h-1), 2^h-1】,最后一层最少一个。

完全二叉树不一定是满二叉树

小结论

• 任意一个二叉树，如果度为0的节点有n0个，度为2的节点有n2个。那么n0=n2+1。

• 完全二叉树，n1要么为0要么为1。

• 不存在度大于二的节点

二叉树的存储方式

• 链式存储
• 顺序存储

二叉树顺序存储是用数组来存储，现实使用只有堆才会用数组来存储。在物理上是数组，在逻辑上是二叉树。

逻辑结构是树的形状，是想象出来的。

物理结构在内存中是用数组存储的。数组表示二叉树仅适用完全二叉树。

​ 物理存储的下标关系：

​ parent=(child-1)/2 两个孩子算出来的整数部分都是相同的

​ leftchild=parent*2+1

​ rightchild=parent*2+2

数组可以存储二叉树，会浪费很多空间。数组存储表示只适用于完全二叉树。

---

堆

堆总是一个完全二叉树。

小根堆：树中所有父亲都小于等于孩子

大根堆：树中所有父亲都大于等于孩子。堆不一定有序。

操作的是数组，插入数据需要与父辈比较，讨论是否需要交换位置。

堆的实现(以大根堆为例)

Heap.h文件

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php);
void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP php);
HPDataType HeapTop(HP* php);
bool HeapEmpty();
int HeapSize();

Heap.c文件

实现插入功能PUSH需要向上调整，向上调整最多调logN次。

实现删除功能POP需要向下调整，向下调整最多调logN次。需要和孩子中较大第一个数交换。

#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"

/*---大堆---*/
void HeapInit(HP* php)//初始化堆
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);//千万记得要记得*4
	if (php->a == NULL)
	{
		perror("malloc failed");
		return;
	}

	php->size = 0;
	php->capacity = 4;
}

/*简单的交换函数*/
void Swap(HPDataType* p1, HPDataType* p2)//交换函数
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

/*向上调整*/
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])//通过比较孩子与父亲的数值大小进行交换
		{
			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, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc failed");
			return;
		}

		php->a = tmp;
		php->capacity *= 2;
	}

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

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

}

/*向下调整*/
void AdjustDown(HPDataType* a, int n, int parent)//n是指堆除去删除后内容的大小，parent从0开始。
{
	int child = parent * 2 + 1;
	while (child < n)//确保子代不超过限额
	{
		if (child+1<n && a[child] < a[child + 1])//右孩子大于左孩子,要检查是否一定有右孩子。
		{
			++child;//取最大的孩子的下标
		}
		if(a[child]>a[parent])//如果最大的孩子大于
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

/*--删除堆顶/删根--*/
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);
}

/*--打印函数--*/
void HeapPrint(HP php)
{
	HPDataType x = php.size;
	for (int i = 0; i < x; i++)
	{
		printf("%d ", php.a[i]);
	}
	printf("\n");
}

/*打印函数*/
//void HeapPrint(HP* php)
//{
//	HPDataType x = php->size;
//	for (int i = 0; i < x; i++)
//	{
//		printf("%d ", php->a[i]);
//	}
//
//}

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

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

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

Test.c文件

#include "heap.h"
int main()
{
	HP hp;
	HeapInit(&hp);

	/*插入*/
	HeapPush(&hp, 1);
	HeapPush(&hp, 5);
	HeapPush(&hp, 6);
	HeapPush(&hp, 7);
	HeapPush(&hp, 9);
	HeapPush(&hp, 2);
	HeapPush(&hp, 29);
	HeapPush(&hp, 72);
	HeapPush(&hp, 1022);
	HeapPrint(hp);

	/*删除*/
	HeapPop(&hp);
	HeapPrint(hp);


	/*-由高到低输出-*/
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}

	return 0;
}

堆的排序

时间负责度为O(N*logN)，冒泡排序的时间复杂度为O(N*N)

升序排列最好建立大堆。

先交换首尾，再向下调整选出次大

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;


/*---大堆---*/
void HeapInit(HP* php)//初始化堆
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);//千万记得要记得*4
	if (php->a == NULL)
	{
		perror("malloc failed");
		return;
	}

	php->size = 0;
	php->capacity = 4;
}

/*简单的交换函数*/
void Swap(HPDataType* p1, HPDataType* p2)//交换函数
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

/*向上调整*/
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

/*向下调整*/
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])//右孩子大于左孩子,要检查是否一定有右孩子
		{
			++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)
{
	HP hp;
	HeapInit(&hp);

	/*-向上调整建堆-*/
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);//将数据输入进堆
	}

	/*-向下调整-*/
	int end = n - 1;//最后一个数据的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}

}

int main()
{
	int a[10] = { 2,1,5,6,3,4,7,8,9,0 };

	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	HeapSort(a, 10);

	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}