【数据结构】堆

目录

一、树的介绍以及堆

1.树

2.二叉树以及堆

二、堆的实现

1.heap.h

2.heap.c 

1)堆的初始化和销毁

2） 堆的插入

3）堆的删除 

4）取堆顶数据

5）堆的数据个数

6）堆的判空

3.test.c 

---

一、树的介绍以及堆

1.树

在了解堆前，我们先来看看树的概念，树是一种非线性的数据结构，它是由n（n>=0）个有限结点（树中的每个元素称为结点）组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

特点：

⭐有一个特殊的结点，称为根结点，根结点没有前驱结点

⭐除根结点外，其余结点被分成M（M>0）个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti（1 <= i <= m）又是一个结构与树类似的子树。每棵子树的根结点有且仅有一个前驱，可以有0个或多个后继

⭐树是递归定义的

 需要注意的是：树形结构中，子树不能有交集，否则就不是树形结构。

接下来看看有关树的相关概念：

结点的度：一个结点含有的子树的个数称为该结点的度，例如上图中的A，其结点的度为6

叶结点或终端结点：度为0的结点称为叶结点，如上图中：B、C、H、I...等为叶结点

非终端结点或分支结点：度不为0的结点，如上图中：D、E、F...等结点为分支结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点，如上图中：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点，如上图：B是A的孩子结点

兄弟结点：具有相同父结点的结点互称为兄弟结点，如上图：B、C是兄弟结点

树的度：一棵树中，最大的结点的度称为树的度，如上图：树的度为6

结点的层次：从根开始·定义起，根为第1层，根的子结点为第2层，以此类推

树的高度和深度：树中结点的最大层次，如上图：树的高度为4

堂兄弟结点：双亲在同一层的结点互为堂兄弟，如上图：H和I互为堂兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点，如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙，如上图，所有结点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示：

树的表示方法有很多，最常用的是孩子兄弟表示法。

typedef int DataType;
struct Node
{
        struct Node* _firstChild1;   // 第一个孩子结点
        struct Node* _pNextBrother;   // 指向其下一个兄弟结点
        DataType _data;   // 结点中的数据域
};

2.二叉树以及堆

二叉树是一种特殊的树形结构，在普通的树形结构中，除了根结点外，每个结点都可能有很多的直接后继，且每个结点都有且只有一个直接前驱。然而，在二叉树中，每个结点的度（即直接后继的数量）不超过2，也就是说，每个结点最多有两个子结点，通常称为左孩子和右孩子。此外，二叉树的子树分左右，且左右次序不能交换，这也是它与普通树的一个主要区别。

 特殊的二叉树：

1）满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2^k-1（2^0 + 2^1 + 2^3 +...+ 2^(k-1)），则它就是满二叉树。

2）完全二叉树：完全二叉树是一种特殊的二叉树结构，它的特点是除了最后一层外，其他各层的节点数都达到最大个数，并且最后一层的节点都连续集中在最左边。若设二叉树的深度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。

二叉树的性质：

①若规定根结点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点

②若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h-1

③对任何一棵二叉树，如果叶结点（度为0）个数为n0，度为2的分支结点个数为n2，则有n0=n2+1（可根据上图验证）

④若规定根结点的层数为1，具有n个结点的满二叉树的深度h = log2（n+1）（以2为底，n+

为对数）（推导：n = 2^0 + 2^1 + 2^3 +...+ 2^(h-1) = 2^h-1）

⑤对于具有n个结点的完全二叉树，如果按照从上至下、从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：若i>0，i位置结点的双亲序号为（i-1）/2，其左右孩子序号分别为2*i+1和2*i+2

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树就适合用顺序结构来存储。现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是，这里的堆和操作系统虚拟进程空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆是一棵完全二叉树，堆中某个结点的值总是不大于（称为小堆）或不小于（称为大堆）其父结点的值。

二、堆的实现

我们按照惯例来建立一个头文件（heap.h）和两个源文件（heap.c和test.c），heap.h用于函数声明，heap.c中写函数体，test.c用来测试。接下来我们就以小堆来讲解代码，其实大堆小堆差别不大，只是调整时控制条件（大于、小于）不同。

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;  //空间大小
}Heap;


// 堆的初始化
void HeapInit(Heap* hp);

// 堆的销毁
void HeapDestory(Heap* hp);

// 堆的插入
void HeapPush(Heap* hp, HPDataType x);

// 堆的删除
void HeapPop(Heap* hp);

// 取堆顶的数据
HPDataType HeapTop(Heap* hp);

// 堆的数据个数
int HeapSize(Heap* hp);

// 堆的判空
bool HeapEmpty(Heap* hp);

2.heap.c 

1)堆的初始化和销毁

// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}


// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

2） 堆的插入

堆的插入与顺序表的插入有点类似，但是不完全相同。同样地，我们在插入前需要先判断是否需要扩容，然后在末尾插入新数据。不同的是，每次插入后需要调整为小堆，因为你插入的数据可能很小，就需要往上调整。

往上调整时，我们传两个参数，一个是数组的地址，一个是孩子（新数据）所在下标，通过child可以找到parents下标，即parents = （child - 1）/ 2，然后不断向上调整并交换数据，那么什么时候循环结束呢？答案是child = 0 时，当child为0时，前边已经没有parents了。

由于后边删除也需要交换数据，我们将实现数值交换功能的函数单独写出来，向下调整的函数也单独拿出来。

//交换
void swap(HPDataType* x, HPDataType* y)
{
	HPDataType t = 0;
	t = *x;
	*x = *y;
	*y = t;
}


//向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parents = (child - 1) / 2;

	//循环控制条件不能是child>=0，当child=0时，parents=（child-1）/2=0
	//虽然这样最后也可以通过break出循环，但是不准确，正确的写法是child>0
	while (child > 0)
	{
		if (a[child] < a[parents])
		{
			//交换
			swap(&a[child], &a[parents]);
			child = parents;
			parents = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}





// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//插入前判断是否需要扩容
	if (hp->size == hp->capacity)
	{
		//扩容
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* arr = realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (arr == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = arr;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	//插入后需要向上调整，保持小堆
	//尾插影响的是祖先（从根到该节点所经分支上的所有节点）
	AdjustUp(hp->a, hp->size - 1);
}

3）堆的删除 

堆的删除是删除堆顶元素，可能很多人的第一想法会是直接删除第一个数据，然后像顺序表中那样直接挪动数据，但是，在堆中这样是错误的，因为堆中的每个数据间是有一定关系的，如果真的直接删除再挪动的话，原本下标为1和下标为2的数据是兄弟关系，挪动后，下标分别变成了0和1，即父子关系然后再对这些数据进行操作就都乱套了，所以这种做法是绝对不行的。

正确的做法是：先交换堆顶元素和最后一个元素的值，然后尾删，删完后向下调整。

 在向下调整的函数中传三个参数，第一个是存放数据的数组地址，第二个是数据个数，第三个是父亲的下标，通过父亲的下标可以找到孩子的下标，然后进行比较和交换。需要注意的是，有两个孩子，我们要找到较小的那个孩子进行比较（因为是小堆）。当孩子的下标超出数据个数时，就结束循环。

//向下调整
void AdjustDown(HPDataType* a, int size, int parents)
{
	int child = parents * 2 + 1;//左孩子

	while (child < size)
	{
		//如果右孩子更小，交换
		//注意child+1<size这个条件，实际最多只能访问到size-1的数据
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parents])
		{
			swap(&a[child], &a[parents]);
			parents = child;
			child = parents * 2 + 1;
		}
		else
		{
			break;
		}
	}
}



// 堆的删除
void HeapPop(Heap* hp)
{
	//删除第一个元素，但是如果只是简单删除，然后移动数组，最后会造成兄弟成父子的情况
	//正确的做法是先交换首元素和最后一个元素，然后删尾，再向下调整
	//向下调整的过程，需要找最小的值，因为堆顶元素是整个堆中的最小元素
	//在左右孩子中找到较小的那个，按照这个方法一直往下找，直到其下标大于size结束
	assert(hp);
	assert(hp->size > 0);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	//向下调整
	AdjustDown(hp->a,hp->size,0);
}

4）取堆顶数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}

5）堆的数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

6）堆的判空

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

3.test.c 

#define _CRT_SECURE_NO_WARNINGS 1

#include "heap.h"

int main()
{
	HPDataType a[] = { 60,30,40,25,48 };
	Heap hp;
	
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}

	HeapDestory(&hp);
	return 0;
}

测试结果：