【数据结构】 -- 堆 （堆排序）（TOP-K问题）

引入

要学习堆，首先要先简单的了解一下二叉树，二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。它具有以下特点：

1. 根节点（Root）：树的顶部节点，没有父节点。
2. 子节点（Children）：每个节点最多有两个子节点，分别称为左子节点和右子节点。
3. 叶子节点（Leaf）：没有子节点的节点称为叶子节点。
4. 父节点（Parent）：每个节点都有一个父节点，除了根节点。
5. 深度（Depth）：从根节点到某个节点的唯一路径的长度，根节点的深度为0。
6. 高度（Height）：从某个节点到它的最远叶子节点的路径长度，叶子节点的高度为0。
7. 遍历（Traversal）：遍历二叉树是指按照一定顺序访问树中的每个节点，常见的遍历方式包括前序遍历、中序遍历和后序遍历。

二叉树的应用非常广泛，在后面我会详细介绍。

满二叉树：除了叶子结点外，每个结点都有两个子结点

一个深度为k的满二叉树有2的k次方减一个节点。

完全二叉树：除了最底层可能不是满的外，其它每一层从左到右都是满的。

满二叉树是完全二叉树的子集，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 

堆就是一种完全二叉树。

二叉树的储存

逻辑结构和物理结构

逻辑结构和物理结构是计算机科学中两个重要的概念，它们描述了数据在计算机中的不同组织方式。

1. 逻辑结构：

   • 逻辑结构是指数据元素之间的相互关系和操作规则。它关注的是数据之间的逻辑关联，而不考虑数据在计算机内部的存储方式。
   • 常见的逻辑结构包括线性结构、树形结构和图形结构。
   • 线性结构中的数据元素之间是一对一的关系，例如线性表、栈、队列等。
   • 树形结构中的数据元素之间存在一对多的关系，例如二叉树、B树等。
   • 图形结构中的数据元素之间是多对多的关系，例如图、网络等。

2. 物理结构：

   • 物理结构描述了数据在计算机内部存储的方式和组织形式，也称为存储结构。
   • 物理结构与计算机的存储器相关，它包括了数据元素在内存中的存储位置和存储方式。
   • 常见的物理结构包括顺序存储结构和链式存储结构。
   • 顺序存储结构是将数据元素连续地存储在内存中的一块连续的存储空间中，例如数组。
   • 链式存储结构是通过指针将数据元素存储在内存中的不同位置，并通过指针将它们串联起来，例如链表。

逻辑结构关注数据之间的逻辑关系和操作规则，而物理结构关注数据在计算机内部的实际存储方式和组织形式。

二叉树的储存

二叉树有多种存储方式，常见的包括顺序存储和链式存储。

1. 顺序存储： 顺序存储通常使用数组来表示二叉树。假设树的根节点存储在数组下标为0的位置，则对于任意一个下标为i的节点：

   • 其左子节点的下标为2i + 1
   • 其右子节点的下标为2i + 2 例如，如果要存储二叉树的节点值为[1, 2, 3, 4, 5, 6, 7]的完全二叉树，可以使用数组[1, 2, 3, 4, 5, 6, 7]进行存储。

2. 链式存储： 链式存储则是通过节点之间的引用来表示二叉树的结构，每个节点包含数据域和左右子节点指针域。

链式储存我们放在后边更新，在这里我们先学习顺序储存。

顺序储存

顺序储存用数组来储存，顺序存储一般只适合用来存储完全二叉树（堆），用顺序储存再存储非完全的二叉树会存在空间浪费

 堆的实现

头文件：

#define _CRT_SECURE_NO_WARNINGS 1
 
#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 HPInit(HP* php);
 
//插入数据
void HPPush(HP* php, HPDatatype x);
 
//交换
void Swap(HPDatatype* a,HPDatatype * b);
 
//销毁
void HPDestroy(HP* php);
 
//向上调整
void AdjustUp(HPDatatype* a, int child);
 
//向下调整
void AdjustDown(HPDatatype* a,int n, int parent);
 
 
//删除顶部数据
void HPPop(HP* php);
 
//返回顶部数据
HPDatatype* HPTop(HP* php);
 
//判空
bool HPEmpty(HP* php);

实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
 
// 初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
 
}
 
//插入数据
void HPPush(HP* php, HPDatatype x)
{
	assert(php);
	//判断空间够不够
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDatatype* tmp = (HPDatatype* )realloc(php->a,newcapacity * sizeof(HPDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;
	
	AdjustUp(php->a, php->size - 1);
}
 
//交换
void Swap(HPDatatype* a, HPDatatype* b)
{
	HPDatatype cmp = *a;
	*a = *b;
	*b = cmp;
}
 
//销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
 
//向上调整
void AdjustUp(HPDatatype* 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;
		}
	}
}
 
//向下调整
void AdjustDown(HPDatatype* a, int n, int parent)
{
	int child = 2 * parent + 1;//先假设左边的小
 
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])//规避chlid + 1 越界的风险
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
 
}
 
 
//删除顶部数据
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;
}

TOP-K问题

一般来说，堆分为两类

1. 大堆（Max Heap）：在最大堆中，每个节点的值都大于或等于其子节点的值。换句话说，堆顶部的元素是整个堆中的最大值。最大堆常用于实现优先队列，其中具有最高优先级的元素始终位于堆顶。

2. 小堆（Min Heap）：在最小堆中，每个节点的值都小于或等于其子节点的值。因此，堆顶部的元素是整个堆中的最小值。最小堆也常用于优先队列，其中具有最低优先级的元素位于堆顶。

简单来说大堆中，同一个分支中大的在上；小堆中，同一分支小的在上。

在这里以小堆为例：

向上调整算法

往堆中插入一个数据时，先将插入的数据放到堆的最后一个节点，然后利用向上调整算法依次调整。

图示：

只要子节点不越界循环一直进行，当字节点不小于父节点时跳出if()语句进入else，跳出循环。

//向上调整
void AdjustUp(HPDatatype* 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;
		}
	}
}

求一堆数据(储存在小堆中)中最最小的前几个数据：将数据插入堆中，小堆的堆顶中储存的就是堆中最小的数据，把堆顶的数据取下来，再将堆顶的数据释放；用向上调整算法调整堆，再依次取堆顶，重复。

//TOP-K
void HPtest02()
{
	int a[] = { 5,6,1,4,2,8 };
	HP s;
	HPInit(&s);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&s, a[i]);
	}
	int k = 0;
	scanf("%d", &k);
	while (k--)
	{
		printf("%d ", HPTop(&s));
		HPPop(&s);
	}
	HPDestroy(&s);
}
 
 
int main()
{
	HPtest02();
 
	return 0;
}

 演示：

在TOP-K问题中，我们会发现，输出的数据是按顺序拍好的，那么我们可不可以在此基础上进行排序呢。 把数据储存到堆中之后，再依次拿出来。

//排序
void HPtest03()
{
	int a[] = { 5,6,1,4,2,8 };
	HP s;
	HPInit(&s);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&s, a[i]);
	}
	int i = 0;
	while (!HPEmpty(&s))
	{
		a[i++] = HPTop(&s);
		HPPop(&s);
	}
	HPDestroy(&s);
}
int main()
{
	
	HPtest03();
	
	return 0;
}

这样我们就可以对数据进行排序。

这个算法的时间复杂度非常低 。 一个有k个节点的对的深度为log（k），一条分支最多交换log (k) - 1次，所以

算法的时间复杂度为log N。 但是这并不能称作真正的排序，因为它在原数组的基础上开辟了新的空间。

堆排序

建堆算法

//堆排序
void HeapSort(int* a, int n)
{
	//建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
}
 
void Heaptset()
{
	int a[] = { 5,6,8,4,1,2,3 };
	HeapSort(a, 7);
}
int main()
{
	//HPtest01();
	/*HPtest02();*/
	//HPtest03();
	Heaptset();
	return 0;
}

排序

在惯性思维中，要排降序应该会建大堆，排升序会建小堆。但这样会导致一个问题（以建排降序 为建小堆为例）

小堆的堆顶为这组数据中最小的数，我们将它取出，作为排序的第一个数

取出堆顶后，找出第二小的数据， 但是此时的堆各个节点已经不满足之前的大小关系了，4之前是6和5的父节点，比6和5大，但是与2为兄弟节点，兄弟节点之间的大小关系原来并不清楚，无法直接找出第二大的数据（可以重新把剩下的数据建堆，但是没必要，时间成本大）。在堆排序中不能让第一个数据直接拿出去，这样会改变节点之间的父子关系，不能确定大小关系，无法找出需要的节点。

接下来以排降序排降序为例演示过程。

//堆排序
void HeapSort(int* a, int n)
{
	//建堆
	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;
	}
}
 
void Heaptset()
{
	int a[] = { 5,6,8,4,1,2,3 };
	HeapSort(a, 7);
}
int main()
{
	//HPtest01();
	/*HPtest02();*/
	//HPtest03();
	Heaptset();
	return 0;
}

调试：

向下调整算法的时间复杂度为log N,堆排序在最坏的情况下N个数据要排N次，所以堆排序的时间复杂度为N log N。可以极大的提高程序的效率。