【数据结构】二叉树的顺序结构实现及时间复杂度计算（二）_二叉树时间复杂度

目录

一，二叉树的顺序结构实现

        1，二叉树的顺序结构

        2，堆的概念及结构

        3，堆的接口实现

1，堆的创建

2，接口函数

3，初始化

4，销毁

5，是否增容

6，交换数据

7，堆向上调整算法

8，插入数据

9，删除数据

10，堆向下调整算法

11，打印数据

12，取堆顶元素

13，判空

14，数据个数

        4，源代码

1，Heap.h

2，Heap.c

二，建堆的时间复杂度

        1，堆的创建

1，向上调整建堆法：

2，向下调整建堆法

        2，向上调整建堆的时间复杂度

        3，向下调整建堆的时间复杂度

三，堆的应用

        1，堆排序

1，建堆

2，利用堆交换删除思想来进行排序

        2，TOP-K问题

---

一，二叉树的顺序结构实现

        1，二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储；

二叉树的顺序储存结构就是用一堆数组储存二叉树中的结点，并且结点的储存位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等；

        2，堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段；

如果有一个关键码的集合K = {k0 ，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足父亲结点的值大于等于或者小于等于子孙结点的值，则称为大堆（或小堆）；

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆；

堆的性质：

1，堆中某个结点的值总是不大于或不小于其父结点的值；

2，堆总是一棵完全二叉树；

        3，堆的接口实现

1，堆的创建

//堆(二叉树)的基本顺序结构
//动态顺序表
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

首先创建一个结构体表示顺序表，这里我们将数据类型重命名为HPDataType，便于我们后续对顺序表数据类型的修改；

a为类型指针代表一维数组；

size为有效数据个数，capacity储存数据的最大容量值；

2，接口函数

// 小根堆
// 堆初始化
void HPInit(HP* php);
// 销毁
void HPDestroy(HP* php);
// 是否增容
void HPCapacity(HP* php);
// 交换数据
void swap(HPDataType* x, HPDataType* y);
// 向上调整
void AdJustUp(HPDataType* a, int size);
// 插入数据
void HPPush(HP* php, HPDataType x);
// 向下调整
void AdJustDown(HPDataType* a, int size, int parent);
// 删除数据
void HPPop(HP* php);
// 打印数据
void HPPrint(HP* php);
// 取堆顶元素
HPDataType HPTop(HP* php);
// 判空
int HeapEmpty(HP* php);
// 数据个数
int HPSize(HP* php);

这里我们实现小根堆，大小根堆的实现原理都一样；

以上是要实现的接口函数；

3，初始化

	//定义
	HP hp;
	//初始化
	HPInit(&hp);

// 堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	php->size = 0;
	php->capacity = 4;
}

首先要进行断言php不能为空，如果php为空则下面对php解引用就会报错；

刚开始先给 a 申请4个HPDataType大小的空间，这个自己可以任意修改，然后对size和capacity进行赋值；

易错点：给指针a申请的是HPDataType大小的空间而不是HP大小的空间，这里由于学习过链表的缘故就容易搞混淆；

4，销毁

// 堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

然后就是销毁顺序表，直接用 free 释放掉 a 即可，再置为空指针，再重置 size 和 capacity ；

5，是否增容

//是否增容
void HPCapacity(HP* php)
{
	assert(php);
	if (php->size == php->capacity)
	{
		php->a = (HPDataType*)realloc(php->a,sizeof(HPDataType)*(php->capacity * 2));
		if (php->a == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		php->capacity *= 2;
	}
}

像后面如果进行数据插入的话，就需要检查空间是否需要增容了，也很好判断，当size等于capacity时就需要增容了，我们这里是选择直接扩容一倍；

然后再更新一下capacity的值就行了；

6，交换数据

//交换数据
void swap(HPDataType* x, HPDataType* y)
{
	assert(x&&y);
	HPDataType z = *x;
	*x = *y;
	*y = z;
}

老样子先对指针x和y进行断言，然后定义z完成x与y的值交换，交换数据后续会使用到；

7，堆向上调整算法

//向上调整
void AdJustUp(HPDataType* a,int size)
{
	assert(a);
	int child = size-1;
	while (child>0)
	{
		int parent = (child - 1) / 2;
        //孩子与父亲比较值
		if (a[child] < a[parent])
		{
            //交换
			swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

先断言，当向堆中插入数据，数据需要与父亲结点进行比较调整；

我们传入指针a，数据个数size，size用来确定插入数据的下标；

然后建立循环遍历，父亲（parent）结点的下标为孩子（child）结点的下标减一除以二：

parent=（child -1）/ 2；

当a[child]的值小于a[parent]的值则进行交换，此时parent的身份转变为child继续向上调整，当child小于等于0，此时已到顶点无需再进行调整，退出循环；

8，插入数据

//插入数据
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//是否增容
	HPCapacity(php);
	php->a[php->size] = x;
	php->size++;
    //向上调整
	AdJustUp(php->a, php->size);
}

首先判断是否需要增容，此时size的值就是末尾的数的下标加一；

直接对其下标进行赋值，再让size加一；

然后就需要将新数据向上调整，相当于更新维护堆结构；

9，删除数据

//删除数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
    //交换数据值
	swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
    //向下调整
	AdJustDown(php->a, php->size,0);
}

删除堆顶数据；

我们要删除数据不能直接删除否则会破坏堆结构，重新调整代价太大（时间复杂度太大)；

我们可以将插入的数据与堆顶的数据进行交换，然后再让size--相当于删除了堆顶数据，然后再让堆顶的数据向下进行调整，以此来更新维护堆结构；

10，堆向下调整算法

//向下调整
void AdJustDown(HPDataType* a, int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child<size)
	{
		//左孩子与右孩子比较值
		if (child+1<size && a[child]>a[child + 1])
		{
			child++;
		}
		//孩子与父亲比较值
		if (a[child] < a[parent])
		{
			//交换
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

孩子(child) 的下标等于父亲(parent) 的下标×2+1：child=parent*2+1；

建立循环遍历数组，先令左孩子为要与父亲比较的孩子，然后如果右孩子存在再让左孩子与右孩子进行比较，选出值小的孩子；

然后让孩子与父亲进行比较，如果孩子小于父亲则进行值的交换，此时孩子的身份变成父亲，继续循环；

当孩子的值大于等于size时循环结束，或者当孩子大于等于父亲则跳出循环；

11，打印数据

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

堆是个顺序表；

size是数据个数，然后进行遍历打印即可；

12，取堆顶元素

//取堆顶元素
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

直接返回堆顶的数据即可；

13，判空

//判空
int HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

直接返回 size是否等于0的判断结果即可，如size等于0则为真，不等于0则为假；

14，数据个数

//数据个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

直接返回size即可；

        

        4，源代码

1，Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
//堆(二叉树)的基本顺序结构
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
// 小根堆
 
// 堆初始化
void HPInit(HP* php);
// 销毁
void HPDestroy(HP* php);
// 是否增容
void HPCapacity(HP* php);
// 交换数据
void swap(HPDataType* x, HPDataType* y);
// 向上调整
void AdJustUp(HPDataType* a, int size);
// 插入数据
void HPPush(HP* php, HPDataType x);
// 向下调整
void AdJustDown(HPDataType* a, int size, int parent);
// 删除数据
void HPPop(HP* php);
// 打印数据
void HPPrint(HP* php);
// 取堆顶元素
HPDataType HPTop(HP* php);
// 判空
int HeapEmpty(HP* php);
// 数据个数
int HPSize(HP* php);
 

2，Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
 
//堆初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	php->size = 0;
	php->capacity = 4;
}
//销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
//交换数据
void swap(HPDataType* x, HPDataType* y)
{
	assert(x&&y);
	HPDataType z = *x;
	*x = *y;
	*y = z;
}
//向上调整
void AdJustUp(HPDataType* a,int size)
{
	assert(a);
	int child = size-1;
	while (child>0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}
//是否增容
void HPCapacity(HP* php)
{
	assert(php);
	if (php->size == php->capacity)
	{
		php->a = (HPDataType*)realloc(php->a,sizeof(HPDataType)*(php->capacity * 2));
		if (php->a == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		php->capacity *= 2;
	}
}
//插入数据
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//是否增容
	HPCapacity(php);
	php->a[php->size] = x;
	php->size++;
	AdJustUp(php->a, php->size);
}
 
//向下调整
void AdJustDown(HPDataType* a, int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child<size)
	{
		//左孩子与右孩子比较值
		if (child+1<size && 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 HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	AdJustDown(php->a, php->size,0);
}
//打印数据
void HPPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
}
//取堆顶元素
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
 
//判空
int HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
 
//数据个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

二，建堆的时间复杂度

        1，堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

int a[] = { 7,8,3,5,1,9,5,4 };
HPSort(a, sizeof(a) / sizeof(a[0]));

1，向上调整建堆法：

//建堆--向上调整建堆 
int num = n;
for (int i = 1; i <= num; i++)
{
    //向上调整
	AdJustUp(a,i);
}

直接一直循环插入数据即可；

2，向下调整建堆法

//建堆--向下调整建堆  O(N)
int num = n;
for (int i = (num - 1 - 1) / 2;i >= 0; i--)
{
	//向下调整
	AdJustDown(a,n,i);
}

需要先把根结点下面的子树都搞成堆，所以先从倒数的第一个非叶子节点的子树开始向下调整，然后循环遍历让结点逐渐缩减（逐渐往上走）向下调整，如图所示；

        2，向上调整建堆的时间复杂度

  F(h)=2^1*1+2^2*2+...+2^(h-2)*(h-2)+2^(h-1)*(h-1)

2*F(h)=2^2*1+2^3*2+...+2^(h-1)*(h-2)+2^h*(h-1)

两式错位相减：

F(h)= - 2^1-2^2-2^3-...-2^(h-2)-2^(h-1)+2^h*(h-1)

F(h)= - 2^h+2-2^h+2^h*h

F(h)=2^h(h-2)+2

假设树有N个结点：2^h-1=N      h=log(N+1)

F(N)=(N+1)*(log(N+1)-2) + 2 ≈ N*logN

所以用向上调整建堆的时间复杂度为O(N*logN);

        3，向下调整建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

则需要移动结点总的移动步数为：

T(n) = 2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+2^3*(h-4)+...+2^(h-3)*2+2^(h-2)*1

2*T(n)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+...+2^(h-2)*2+2^(h-1)*1

两式错位相减：

T(n)=1-h+2^1+2^2+2^3+2^4+...+2^(h-2)+2^(h-1)

T(n)=2^h-1-h

n=2^h-1  ==  h=log(n+1)

T(n)=n-log2(n+1)≈n

所以用向下调整建堆的时间复杂度为O(N);

由此可见，建堆的时间复杂度为O(N)！

三，堆的应用

        1，堆排序

1，建堆

升序：建大堆

降序：建小堆

2，利用堆交换删除思想来进行排序

int num = n;
while (num>1)
{
	//交换数据
	swap(&a[0], &a[num-1]);
	num--;
	//向下调整
	AdJustDown(a,num,0);
}

其实很简单，比如我们要整一个升序数组，有人会说建小堆，其实这是错的；

如果建小堆：堆顶的数不变，找次大的数要将堆顶以下的数全部重新排序，这不现实，所以pas；

建大堆：将堆顶的数据与末尾的数据交换，然后令num--（将末尾的数隔离开），再将堆顶的数向下调整，然后循环遍历一直找次大的数，当num等于1时堆顶的数为最小值，此时的数组便是升序数组！

这就是堆的交换删除思想，这个循环的时间复杂度为O(N*logN)

        2，TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决;

正常思路：

把这个N建成大堆，PopK次，即可找出最大的前K个

但是，当N非常大时，假设N时10亿，那就是10亿个整数，所需的空间太大了，不可取！

优化思路：

1，将前K个数建成小堆

2，后面将N-K个数依次与堆顶的数据进行比较，如比堆顶的数据大，则替换他为堆顶，然后向下调整

3，最后比较完了，这个小堆的值就是最大的前K个！

第二阶段就到这里了，下面更新二叉树的链式结构的实现；

如有不足之处欢迎来补充交流！

完结。。。

---