二叉树的顺序实现-堆

目录

一、什么是堆

二、堆的实现

2.1 向上调整算法

2.1.1 思路

2.1.2 代码

2.2 向下调整算法

2.2.1 思路

2.2.2 代码

2.3 插入

2.3.1 思路

2.3.2 代码

2.4 删除

2.4.1 思路

2.4.2 代码

三、C语言源码汇总

3.1 heap.h

3.2 heap.c

四、堆的应用-TopK问题

4.1 分析

4.2 C语言源码

---

一、什么是堆

在数据结构中，堆（Heap）是一种特殊的树形数据结构，用数组存储，通常被用来实现优先队列。

堆具有以下特点：

1. 堆是一棵完全二叉树（Complete Binary Tree），即除了最后一层外，其他层都是满的，且最后一层的节点从左到右排列。
2. 堆中的每个节点都满足堆的性质，即父节点的值不小于（或不大于）其子节点的值，这种性质被称为堆序性（Heap Property）。
   • 最大堆（Max Heap）：父节点的值不小于其子节点的值。
   • 最小堆（Min Heap）：父节点的值不大于其子节点的值。
3. 堆中的根节点（通常是位于最顶层的节点）是堆中的最大（或最小）元素。在最大堆中，根节点的值大于等于其子节点的值；在最小堆中，根节点的值小于等于其子节点的值。
4. 堆不保存节点之间的具体顺序，只保证堆序性。
5. 堆可以用数组来表示，根据节点的索引和父子节点的关系可以计算出节点之间的关系。

堆的常见操作有插入（Insert）、删除根节点（Delete Max/Min）和查找最大（或最小）元素。

堆的应用非常广泛，常见的应用包括优先队列、堆排序、图算法（如最短路径算法中的Dijkstra算法）等。通过使用堆，可以高效地在大量数据中插入、删除和获取最大（或最小）元素，时间复杂度为O(log n)。

二、堆的实现

2.1 向上调整算法

2.1.1 思路

以大堆举例：目的是要实现叶子节点要比所有的祖先节点小

• 考虑单次：如果父节点比孩子结点小，则二者交换
• 考虑循环：

1. 循环体：交换之后先前的父亲节点与孩子结点的下标值互换，继续进行单次比较交换
2. 结束条件：
   一般的情况：如果符合大堆的条件（父节点大于子节点），则可以跳出循环。
   最坏的情况：一直交换到了根节点，如果在进行下去数组就会越界，所以下标值应该>=0

2.1.2 代码

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			//下标值互换
            child = parent;
            //重新计算父亲结点的值
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2.2 向下调整算法

2.2.1 思路

以小堆举例：目的是要实现叶子节点要比所有的祖先节点大

• 考虑单次：

1. 先找到孩子节点中较小的结点
2. 如果父节点比孩子结点大，则二者交换

• 考虑循环：

1. 循环体：交换之后先前的父亲节点与孩子结点的下标值互换，继续进行单次比较交换
2. 结束条件：
   一般的情况：如果符合小堆的条件（父节点小于子节点），则可以跳出循环。
   最坏的情况：一直交换到了叶子节点，如果在进行下去数组就会越界，所以下标值应该<=n-1

2.2.2 代码

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[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.3 插入

2.3.1 思路

从物理结构上讲，插入到数组的最后一个位置，然后用向上调整算法调整即可

2.3.2 代码

void HPPush(HP* php, HPDataType x)
{
	assert(php);
 
    //检测数组是否扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		php->a = tmp;
		php->capacity = newcapacity;
	}
    //插入
	php->a[php->size] = x;
	php->size++;
    //调整
	AdjustUp(php->a, php->size - 1);
}

2.4 删除

2.4.1 思路

删除一般删除的是堆顶的元素

如果直接删除，然后用向下调整算法调整：原来的子节点会变成父节点，父节点会变成子节点。所以不可以采取此做法。

正确的做法：将堆顶元素与堆底元素交换，删除掉数组尾部元素，向下调整原数组。这样就可以规避原堆父子关系全乱的问题

2.4.2 代码

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换
    Swap(&php->a[0], &php->a[php->size - 1]);
	//删除
    php->size--;
    //调整
	AdjustDown(php->a, php->size, 0);
}

三、C语言源码汇总

3.1 heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
//结构体定义
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//插入
void HPPush(HP* php, HPDataType x);
//删除
void HPPop(HP* php);
//返回堆顶元素
HPDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);

3.2 heap.c

#include"heap.h"
 
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
 
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
 
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 (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
void HPPush(HP* php, HPDataType x)
{
	assert(php);
 
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a, php->size - 1);
}
 
void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;
 
	while (child < n)  // 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;
		}
	}
}
 
// logN
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
 
	AdjustDown(php->a, php->size, 0);
}
 
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}
 
bool HPEmpty(HP* php)
{
	assert(php);
 
	return php->size == 0;
}

四、堆的应用-TopK问题

4.1 分析

处理的是数据量非常大的情况下，需要知道最大/最小的某几个数的问题。

由于建堆的空间复杂度是O(N)，所以建堆的方式不可行，需要直接在数组上操作。

正确的思路：用前K个数，建一个小堆，剩下的数据跟堆顶数据比较，如果比堆顶的数据大，就替代堆顶进堆（覆盖根位置，然后向下调整）

4.2 C语言源码

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
 
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 10000000;
		fprintf(fin, "%d\n", x);
	}
 
	fclose(fin);
}
 
void TopK()
{
	int k;
	printf("请输入k>:");
	scanf("%d", &k);
	int* heap = (int*)malloc(sizeof(int) * k);
	if (heap == NULL)
	{
		perror("malloc fail");
		return;
	}
	const char* file = "data.txt";
	FILE* num = fopen(file, "r");
	if (num == NULL)
	{
		perror("fopen error");
		return;
	}
 
	// 读取文件中前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(num, "%d", &heap[i]);
	}
 
	// 建K个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(heap, k, i);
	}
 
	// 读取剩下的N-K个数
	int x = 0;
	while (fscanf(num, "%d", &x) > 0)
	{
		//更新小堆的数据并进行算法排序
		if (x > heap[0])
		{
			heap[0] = x;
			AdjustDown(heap, k, 0);
		}
	}
 
	printf("最大前%d个数: ", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", heap[i]);
	}
	printf("\n");
}
 
int main()
{
	CreateNDate();
 
	TopK();
 
	return 0;
}