四川盐亭网站制作公司

数据结构C语言版——二叉树的顺序存储堆的实现-创新互联

文章目录
  • 二叉树顺序结构实现(堆)
    • 1. 堆的概念
    • 2. 堆的基本操作
      • 堆的向下调整算法
      • 堆的创建
      • 堆的向上调整算法
    • 3. 堆的实现
      • 堆的创建
      • 向堆中插入元素
      • 删除堆顶元素
      • 获取堆顶元素
      • 获取堆中元素个数
      • 判断堆是否为空
      • 堆的销毁
    • 4. TopK问题

创新互联是一家专注于网站设计制作、成都网站建设与策划设计,乐山网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:乐山等地区。乐山做网站价格咨询:18982081108
二叉树顺序结构实现(堆) 1. 堆的概念
  • 堆在物理上是一个一维数组，在逻辑上是一颗完全二叉树
  • 满足父亲节点小于等于孩子节点的叫做小堆或者小根堆
  • 满足父亲节点大于等于孩子节点的叫做大堆或者大根堆

堆的孩子和父亲的下标关系

  1. 已知父亲(parent)的下标

    • 左孩子(left)下标等于 l e f t = 2 ∗ p a r e n t + 1 left = 2*parent+1 left=2∗parent+1
    • 右孩子(right)下标等于 r i g h t = 2 ∗ p a r e n t + 2 right = 2 * parent + 2 right=2∗parent+2

  2. 已知左孩子或右孩子下标(child)

    • 父亲节点下标等于 p a r e n t = ( c h i l d − 1 ) / 2 parent = (child-1)/2 parent=(child−1)/2

在这里插入图片描述

2. 堆的基本操作 堆的向下调整算法

下面这个数组逻辑上可以看作是一棵完全二叉树，通过从根节点开的向下调整算法可以把它调整成一个堆(大堆或小堆)，向下调整算法有以有一个前提：左右子树必须是一个堆，才能调整。我这里的是实现小堆的向下调整算法。

建小堆的向下调整的基本思路就是：从堆顶开始，拿自己和较小的一个孩子进行比较大小，如果小就进行交换然后把交换的位置当作父节点继续向下调整，如果两个孩子都比自己小就停止调整，否则一直调整到叶子节点。

在这里插入图片描述

// 向下调整(小堆)
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
	int child = 2 * parent+1;
	while (parent< n)
	{		//找出两个孩子里的较小的
		if (child< n && child + 1< n && arr[child] >arr[child + 1])
		{	child++;
		}
		// 拿较小的孩子比较和父亲比价大小
		if (child< n && arr[child]< arr[parent])
		{	Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{	//说明无需调整
			break;
		}
	}
}

堆的向下调整每次调整的一个节点，假设树的高度为 h h h最坏情况下调整的次数就是 h − 1 h-1 h−1，所以向下调整的时间复杂度就是树的深度 l o g 2 ( n − 1 ) log_{2}(n-1) log2​(n−1)，最后得出 l o g 2 n log_{2}n log2​n

堆的创建

我们知道堆的向下调整算法必须满足左右子树都是一个堆，那有的时候是一个普通的数组，也就是一颗普通的完全二叉树，所以要通过建堆来让一个数组变成堆。

建堆的实现思路：从最后一个节点的父节点，也就是第一个非叶子节点的父亲开始不断向下调整，直到整课树都被调整成一个堆。

在这里插入图片描述

//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)//n为数组元素个数
{AdjustDown(arr,n ,i);
}

建堆的时间复杂度

我们知道时间复杂度就是计算最坏的时间复杂度，实际上就是计算一个满二叉树，这样每一棵树都会进行调整。

假设这一棵树的高度是 h h h

  1. 第一层的节点个数就是 2 0 2^{0} 20、第二层 2 1 2^{1} 21、第三层 2 2 2^{2} 22，第 n n n层就有 2 n − 1 2^{n-1} 2n−1个，那么最后一层就有 2 h − 1 2^{h-1} 2h−1个节点
  2. 每一层调整的高度：第一层 h − 1 h-1 h−1、第二层 h − 2 h-2 h−2、…、1

那么假设时间复杂度为 T n T_{n} Tn​，时间复杂度就是从第一层到倒数第二层每个节点的调整次数之和

  • 时间复杂度： 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 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 T(n)=20∗(h−1)+21∗(h−2)+22∗(h−3)+23∗(h−4)+...+2h−3∗2+2h−2∗1
  • 等式两边同时乘2： 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 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 2∗T(n)=21∗(h−1)+22∗(h−2)+23∗(h−3)+24∗(h−4)+...+2h−2∗2+2h−1∗1
  • 使用错位相减法(将上面两个等式进行相减)： T ( n ) = 2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 h − 2 + 2 h − 1 − h + 1 T(n) = 2^{1}+2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1}-h+1 T(n)=21+22+23+24+...+2h−2+2h−1−h+1
  • 错位相减后得到一个等比数列： T ( n ) = 2 0 + 2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 h − 2 + 2 h − 1 − h T(n) = 2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1}-h T(n)=20+21+22+23+24+...+2h−2+2h−1−h
  • 通过等比数列公式$S_{n} = \frac{a_{1}(1-q^{n})}{1-q} $
  • 1 − 2 ( h − 1 ) ∗ 2 1 − 2 \frac{1-2^{(h-1)}*2}{1-2} 1−21−2(h−1)∗2​
  • T ( n ) = 2 h − 1 − h T(n) = 2^{h}-1-h T(n)=2h−1−h；( h h h是错位相减得到的)
  • 假设有 N N N个节点，于是就推出 N = 2 h − 1 N = 2^{h}-1 N=2h−1,即 h = l o g 2 ( N + 1 ) h =log_{2}(N+1) h=log2​(N+1)（一棵高度为 h h h的满二叉树的节点个数等于 2 h − 1 2^{h}-1 2h−1）
  • 把上面两个公式带入 T ( n ) = 2 h − 1 − h T(n) = 2^{h}-1-h T(n)=2h−1−h得出，得到 T ( n ) = N − l o g 2 ( N + 1 ) T(n) = N - log_{2}(N+1) T(n)=N−log2​(N+1)
  • 通多大O渐近法表示得到最后的时间复杂度 O ( N ) O(N) O(N)

所以建堆的时间复杂度就是 O ( N ) O(N) O(N)，因为当 N N N足够大时，对数的大小就根本不值得一提了。

堆的向上调整算法

堆的向上调整算法是用一个堆中，当我们要在堆的末尾插入一个新元素。

将堆顶元素和最后一个元素进行交换，然后将最后一个位置的元素进行向上调整。

如果是建小堆，拿最后一个元素和父节点进行比较，如果父节点大于自己就进行交换，接着以父节点的位置继续开始向上调整，如果不小于父节点就停止向上调整(说明此时已经满足小堆的条件了)。

在这里插入图片描述

// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
// 向上调整(建小堆)
void AdjustUp(HPDataType* arr, int index)
{int child = index;
	int parent = (child-1) / 2;//获取父节点下标
	while (child >0)
	{if (arr[parent] >arr[child])//如果节点如果大于孩子就交换
		{	Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child-1) / 2;
		}
		else
		{	//说明无需调整
			break;
		}
	}
}
3. 堆的实现

通过一维数组来实现一个逻辑上的完全二叉树，需要定义以下接口

堆的结构体

typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;//数组
	int size;//堆中元素个数
	int capacity;//堆的容量
}Heap;
// 交换函数
void Swap(HPDataType* x, HPDataType* y);
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n);
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index);
// 向上调整
void AdjustUp(HPDataType* arr, int index);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType data);
// 堆的删除
void HeapPop(Heap* hp);
// 获取堆顶元素
HPDataType HeapTop(Heap* hp);
// 获取堆的元素个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
堆的创建

首先先通过malloc开辟空间

如果一个数组不是堆，在创建的时候就需要通过向下调整算法，从最后一个叶子节点的父亲开始调整，把它调整成一个小堆

// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
	Heap* heap = (Heap*)(malloc(sizeof(Heap)));
	if (heap == NULL)
	{printf("malloc erro!\n");
		exit(-1);
	}
	heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
	heap->size = n;
	heap->capacity = n;
	memcpy(heap->arr, arr, sizeof(HPDataType) * n);
	//向下调整建堆
	int i = 0;
	//从倒数第一个非叶子节点开始向下调整
	for (i = (n - 2) / 2; i >= 0; --i)
	{AdjustDown(heap->arr,heap->capacity ,i);
	}

	return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
	int child = 2 * parent + 1;
	while (parent< n)
	{		//找出两个孩子里的较小的
		if (child< n && child + 1< n && arr[child] >arr[child + 1])
		{	child++;
		}
		// 拿较小的孩子比较和父亲比价大小
		if (child< n && arr[child]< arr[parent])
		{	Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{	//说明无需调整
			break;
		}
	}
}
向堆中插入元素
  • 堆的插入需要判断扩容，如果堆满了就进行二倍扩容。
  • 每次默认在堆的末尾插入一个元素，再拿这个元素进行向上调整
// 堆的插入
void HeapPush(Heap* hp, HPDataType data)
{assert(hp);
	//扩容
	if (hp->size == hp->capacity)
	{// 二倍扩容
		HPDataType* ptr = (HPDataType*)(realloc(hp->arr, sizeof(HPDataType)*hp->capacity * 2));
		if (ptr == NULL)
		{	printf("扩容失败\n %s", strerror(errno));
			exit(-1);
		}
		hp->arr = ptr;
		hp->capacity = 2 * hp->capacity;
	}

	hp->arr[hp->size] = data;
	//向上调整
	AdjustUp(hp->arr,hp->size);
	hp->size++;
}
删除堆顶元素

删堆顶元素实现思路

  • 拿堆顶元素和数组最后一个元素进行交换
  • 在把堆中元素个数减一
  • 再从堆顶进行向下调整
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
	assert(hp && hp->size != 0);

	//拿堆顶元素和数组最后一个元素交换
	Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
	hp->size--;
	//向下调整
	AdjustDown(hp->arr, hp->size, 0);
	
}
获取堆顶元素

这个比价简单，就会返回数组 第一个元素就好

// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);

	return hp->arr[0];
}
获取堆中元素个数
// 获取堆的元素个数
int HeapSize(Heap* hp)
{assert(hp);

	return hp->size;
}
判断堆是否为空
// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);

	return hp->size == 0;
}
堆的销毁
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);
	free(hp->arr);
	hp->size = 0;
	hp->capacity = 0;
	hp->arr = NULL;
	free(hp);
}
4. TopK问题

Topk问题：给你一个组数据找出前k大的数

思路：对数组排序，取出前k个

size_t IntCmp(const void* x, const void* y)
{return *((int*)y) - *((int*)x);
}
void Test(int* arr, int n, int k)
{qsort(arr, n, sizeof(arr[0]), IntCmp);
	int i = 0;
	for (i = 0; i< k; i++)
	{printf("%d ", arr[i]);
    }
}

qsort底层是通过快排实现的，而快排的时间复杂度为 n ∗ l o g 2 n n*log_{2}n n∗log2​n

问题升级：能不能让时间复杂度在降低一点

此时就可以通过堆来解决这个问题

  • 找前k个大的建小堆
  • 找前k个小的建大堆

假设前面的找前k个大的数，建个小堆，因为小堆的堆顶一定是是一组数里最小的一个数字，如果来了一个数字比最小的数还要大，那么它肯定是要先如堆的。

于是写出代码

// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
	Heap* heap = (Heap*)(malloc(sizeof(Heap)));
	if (heap == NULL)
	{printf("malloc erro!\n");
		exit(-1);
	}
	heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
	heap->size = n;
	heap->capacity = n;
	memcpy(heap->arr, arr, sizeof(HPDataType) * n);
	//向下调整建堆
	int i = 0;
	//从倒数第一个非叶子节点开始向下调整
	for (i = (n - 2) / 2; i >= 0; --i)
	{AdjustDown(heap->arr,heap->capacity ,i);
	}

	return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
	int child = 2 * parent;
	while (parent< n)
	{		//找出两个孩子里的较小的
		if (child< n && child + 1< n && arr[child] >arr[child + 1])
		{	child++;
		}
		// 拿较小的孩子比较和父亲比价大小
		if (child< n && arr[child]< arr[parent])
		{	Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent;
		}
		else
		{	//说明无需调整
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
	assert(hp && hp->size != 0);

	//拿堆顶元素和数组最后一个元素交换
	Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
	hp->size--;
	//向下调整
	AdjustDown(hp->arr, hp->size, 0);
	
}

// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);

	return hp->arr[0];
}

然后不断获取堆顶元素，不断删除堆顶元素，就能得到前K个小的数。于是 O ( n ) O(n) O(n)的时间复杂就解决了问题

问题继续升级：假设有100亿个整数，从中找出前10大的数。

此时用单纯用堆肯定行不通的，因为一个整形4个字节，那么100亿个整形就是400亿个字节，那么这就是将近40G的数据，如果单纯用堆肯定是不行的。

思路：建一个大小为10的小堆，不断往堆中插入元素，如果元素满了，就和堆顶比较，如果小就删除堆顶元素，然后再进行插入，直到遍历完整个数组。

那么此时的时间复杂度为 O ( n ) O(n) O(n)，而空间复杂度则是 O ( k ) O(k) O(k)

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章名称：数据结构C语言版——二叉树的顺序存储堆的实现-创新互联
转载源于：http://scyanting.com/article/dhppdj.html

其他资讯