【数据结构】堆（一）——堆的实现

た入场券 2024-03-30 10:08 81阅读 0赞

> 作者：一个喜欢猫咪的的程序员
> 
> 专栏：《数据结构》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![fc94b9869ece4c43b57c0a9d9cf49236.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> 堆的概念及结构：
> 
> 堆的实现思路：（我们以大堆为例）
> 
> 需要实现的接口：
> 
>  实现的一些细节：
> 
> HeapPush函数：
> 
> Ajustup函数：
> 
> HeapPop函数：
> 
> Ajustdown函数： 
> 
> 代码实现：
> 
> Heap.h文件：
> 
> Heap.c文件:
> 
> Test.c文件：
> 
> --------------------

## 堆的概念及结构： ##

如果有一个关键码的集合K = \{ ， ， ，…， \}，把它的所有元素**按完全二叉树的顺序存储方式存储  
在一个一维数组**中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。**将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。**

*  父节点都比其的子节点**大**的完全二叉树叫做**大堆**。
 *  父节点都比其的子节点**小**的完全二叉树叫做**小堆**。

![c8825ad6454d46859a065903ebfdcab4.png][]

**堆的性质：**

*  **堆中某个节点的值总是不大于或不小于其父节点的值；**
 *  **堆总是一棵完全二叉树。**

--------------------

## 堆的实现思路：（我们以大堆为例） ##

### **需要实现的接口：** ###

void Swap(HPDataType* p1, HPDataType* p2);
    void HeapCreate(HP* php, HPDataType* a, int n);
    void HeapPrintf(HP* php);
    void HeapInit(HP* php);
    void HeapDestroy(HP* php);
    void HeapPush(HP* php, HPDataType x);
    void HeapPop(HP* php);
    HPDataType HeapTop(HP* php);
    int HeapSize(HP* hp);
    bool HeapEmpty(HP* hp);
    void Ajustdown(HPDataType* a, int n, int parent); 
    void Ajustup(HPDataType* a, int n);

> 从堆的结构中，我们了解到堆是一个数组**a**，并且后续我们可能需要对数组进行扩容和缩小，因此我们还需要两个变量：有效长度**size**和容量**capacity**

![bc75a8adf5ad43ec975185d2b68f0243.png][]

--------------------

### 实现的一些细节： ###

> HeapInit、HeapDestroy、HeapPrintf函数没有什么好说的。

void HeapInit(HP* php)
    {
    	assert(php);
    	php->capacity = 0;
    	php->size = 0;
    	php->a = NULL;
    }
    void HeapDestroy(HP* php)
    {
    	assert(php);
    	assert(php->a);
    	free(php->a);
    	free(php);
    }
    void HeapPrintf(HP* php)
    {
    	assert(php);
    	for (int i = 0; i < php->size; i++)
    	{
    		printf("%d ", php->a[i]);
    	}
    	printf("\n");
    }

#### HeapPush函数： ####

因为我们的存储结构是一个数组，Push就直接添加数据吗？

当**capacity==size**时扩容一下（包括初始化的方案），当**size==0**时，扩容4个空间，否则扩容二倍的空间，**capacity**也跟着扩大，当push后**size**\++。

![dfcf75c5ed7c48ee83d2ed92be4dd761.gif][]

以大堆为例：

100比30大，30和100需要调换位置，然后100又比70大，70和100需要再次调换位置。

我们添加的数据**x**作为子节点**child**，**child**可能会比它的父节点**parent**大。因此需要将**child向上调整Ajustup。**

void HeapPush(HP* php, HPDataType x)
    {
    	assert(php);
    	if (php->size == php->capacity)
    	{
    		int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity;
    		HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			exit(-1);
    		}
    		php->a = tmp;
    		php->capacity = newcapacity;
    	}
    	php->a[php->size++] = x;
    	Ajustup(php->a, php->size-1);
    }

#### Ajustup函数： ####

![64db6571e02a48a4a9cd6b6be8368b03.png][]

>  *  二叉树的性质：**child=2\*parent+1**
> 
> (可参考我的另外一篇博客：[http://t.csdn.cn/GLlHN][http_t.csdn.cn_GLlHN])

**如果child<parent时，child和parent交换，交换后child=parent。否则break跳出循环。以此循环，当child来到根节点时结束，即：下标为0。**

void Ajustup(HPDataType*a, int child)
    {//N*logN
    	assert(a);
    	//int child = n - 1;
    	while (child > 0)
    	{
    		int parent = (child - 1) / 2;
    		if (a[child] > a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

交换可以写一个函数Swap来复用，会用到很多次。

void Swap(HPDataType* p1, HPDataType* p2)
    {
    	assert(p1);
    	assert(p2);
    	HPDataType tmp = 0;
    		tmp = *p1;
    		*p1 = *p2;
    		*p2 = tmp;
    }

--------------------

#### HeapPop函数： ####

> 出数据只能是出堆顶的元素（根节点），否则没有什么意义。

当我们将根节点删除后，它的左子节点**leftchild**和右子节点**rightchild**谁来当根节点呢？ 并且我们还得维持它是一个堆，也就是**维持它是一个完全二叉树**。

假设左子节点大于右子节点时，让左子节点当根节点会出现什么情况呢？

![c6edf581078b4ec9adab2ec1351505e8.gif][]显然这种方法是不可行的！！！

换一种思路：

**让第一个位置的值和最后一个位置的值，再size--不就相当于删除了嘛，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。**

![b40b09656fb84cba94001928da9d8bca.png][]

void HeapPop(HP* php)
    {
    	assert(php);
    	assert(php->size > 0);
    	Swap(&php->a[0], &php->a[php->size-1]);
    	php->size--;
    	Ajustdown(php->a, php->size-1 , 0);
    }

#### Ajustdown函数： ####

>  *  由性质**child=2\*parent+1**，反推：**parent=（child-1）/2。**

假设左子节点大，左子节点**leftchild**大于右子节点**rightchild** ，当左子节点小于右子节点，**child++**找到子节点大的那一个。

当**parent>child**时交换，**parent=child、child=2\*child+1。**

void Ajustdown(HPDataType* a, int n,int parent)
    {//O(N)
    	assert(a);
    	int child = 2 * parent+1;
    	while (child<n)
    	{
    		if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大
    		{
    			child++;
    		}
    		if (a[child] > a[parent])//>大堆，<为小堆
    		{
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = child * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

> HeapTop、HeapSize、HeapEmpty函数较为直接，就不做解释了。

HPDataType HeapTop(HP* php)
    {
    	assert(php);
    	assert(php->size > 0);
    	return php->a[0];
    }
    int HeapSize(HP* php)
    {
    	assert(php);
    	return php->size;
    }
    bool HeapEmpty(HP* php)
    {
    	assert(php);
    	if (php->size == 0)
    		return true;
    	else
    		return false;
    }

--------------------

## 代码实现： ##

### Heap.h文件： ###

#define  _CRT_SECURE_NO_WARNINGS
    #pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<string.h>
    #include<time.h>
    typedef int HPDataType;
    typedef struct Heap
    {
    	HPDataType* a;
    	int size;
    	int capacity;
    }HP;
    void Swap(HPDataType* p1, HPDataType* p2);
    void HeapCreate(HP* php, HPDataType* a, int n);
    void HeapPrintf(HP* php);
    void HeapInit(HP* php);
    void HeapDestroy(HP* php);
    void HeapPush(HP* php, HPDataType x);
    void HeapPop(HP* php);
    HPDataType HeapTop(HP* php);
    int HeapSize(HP* hp);
    bool HeapEmpty(HP* hp);
    void Ajustdown(HPDataType* a, int n, int parent); 
    void Ajustup(HPDataType* a, int n);

### Heap.c文件: ###

#include"Heap.h"
    void HeapInit(HP* php)
    {
    	assert(php);
    	php->capacity = 0;
    	php->size = 0;
    	php->a = NULL;
    }
    void HeapDestroy(HP* php)
    {
    	assert(php);
    	assert(php->a);
    	free(php->a);
    	free(php);
    }
    void HeapPrintf(HP* php)
    {
    	assert(php);
    	for (int i = 0; i < php->size; i++)
    	{
    		printf("%d ", php->a[i]);
    	}
    	printf("\n");
    }
    void Swap(HPDataType* p1, HPDataType* p2)
    {
    	assert(p1);
    	assert(p2);
    	HPDataType tmp = 0;
    		tmp = *p1;
    		*p1 = *p2;
    		*p2 = tmp;
    }
    void Ajustup(HPDataType*a, int child)
    {//N*logN
    	assert(a);
    	//int child = n - 1;
    	while (child > 0)
    	{
    		int parent = (child - 1) / 2;
    		if (a[child] > a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    void Ajustdown(HPDataType* a, int n,int parent)
    {//O(N)
    	assert(a);
    	int child = 2 * parent+1;
    	while (child<n)
    	{
    		if (child + 1 < n && a[child] < a[child + 1])//  <假设左子树大
    		{
    			child++;
    		}
    		if (a[child] > a[parent])//>大堆，<为小堆
    		{
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = child * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    void HeapCreate(HP* php, HPDataType* a, int n)
    {
    	assert(php);
    	HPDataType*tmp=(HPDataType*)malloc(sizeof(HPDataType) * n);
    	if (tmp == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	memcpy(php->a, tmp, sizeof(HPDataType)*n);
    	php->size = php->capacity = n;
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		Ajustdown(php->a, n, i);
    	}
    }
    void HeapPush(HP* php, HPDataType x)
    {
    	assert(php);
    	if (php->size == php->capacity)
    	{
    		int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity;
    		HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			exit(-1);
    		}
    		php->a = tmp;
    		php->capacity = newcapacity;
    	}
    	php->a[php->size++] = x;
    	Ajustup(php->a, php->size-1);
    }
    void HeapPop(HP* php)
    {
    	assert(php);
    	assert(php->size > 0);
    	Swap(&php->a[0], &php->a[php->size-1]);
    	php->size--;
    	Ajustdown(php->a, php->size-1 , 0);
    }
    HPDataType HeapTop(HP* php)
    {
    	assert(php);
    	assert(php->size > 0);
    	return php->a[0];
    }
    int HeapSize(HP* php)
    {
    	assert(php);
    	return php->size;
    }
    bool HeapEmpty(HP* php)
    {
    	assert(php);
    	if (php->size == 0)
    		return true;
    	else
    		return false;
    }

### Test.c文件： ###

#include"Heap.h"
    void test1()
    {
    	HP php;
    	HeapInit(&php);
    	HeapPush(&php, 75);
    	HeapPush(&php, 56);
    	HeapPush(&php, 30);
    	HeapPush(&php, 25);
    	//HeapPop(&php);
    	int a=HeapSize(&php);
    	printf("%d\n", a);
    	HeapPrintf(&php);
    	HeapPush(&php, 100);
    	HeapPrintf(&php);
    	HeapPop(&php);
    	HeapPrintf(&php);
    	HeapDestroy(&php);
    }
    int main()
    {
    	test1();
    	//test2();
    	//test3();
    	//test4();
    	return 0;
    }

--------------------

[fc94b9869ece4c43b57c0a9d9cf49236.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a35848037ffe4c47bcb0a4dc59dfdd68.jpeg
[c8825ad6454d46859a065903ebfdcab4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a5a4eb71753e499e8515638a8cc70abb.png
[bc75a8adf5ad43ec975185d2b68f0243.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ff354c4b4cf74b3d9eb8b27161a9b104.png
[dfcf75c5ed7c48ee83d2ed92be4dd761.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1d1af853508d4ed08ea81d429d16dccb.gif
[64db6571e02a48a4a9cd6b6be8368b03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/741748515fba4ad9ba7715cd007c53d7.png
[http_t.csdn.cn_GLlHN]: http://t.csdn.cn/GLlHN
[c6edf581078b4ec9adab2ec1351505e8.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dc6e8019a01f4140947fbaacbccf61bd.gif
[b40b09656fb84cba94001928da9d8bca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/434374b80ac8491bb50ee6bdc952edd3.png