【学习笔记】堆（c语言）_c语言堆

1.堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

我们抛去表面看本质：堆就是一种特殊的数组，但在想象中是二叉树的结构，且堆中某个结点的值总是不大于或不小于其父结点的值。

可以看到：在实际数组中，数据看似排列得毫无规律，但在想象中其实它每个结点数据都不大于其父结点的数据。

2.堆的分类

2.1大根堆

大根堆：堆中某个结点的值总是不大于其父结点的值（本文主要以大根堆为例讲解）

2.2小根堆

小根堆：堆中某个结点的值总是不小于其父结点的值

---

3.堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值。

堆总是一棵完全二叉树。

---

4.将数组建成堆

前面说过堆就是一种特殊的数组，那我们想要将数组建成堆就必须做一些特殊处理。

4.1向下调整算法（这里以大堆为例）

先来考虑这样一个问题：当根的左右子树已经是堆，那要怎样才能将整个数组建成堆呢？这就需要用到向下调整算法了。

向下调整算法：在左右子树已经是堆的情况下，找出当前结点的两个子结点中较大的那个，并用当前结点与较大子节点比较，若当前结点比子结点小则交换，持续对当前结点重复以上操作，知道当前结点不再比子结点小。

此时结点‘27’的左右子树都为大堆，对结点‘27’进行向下调整，比较结点‘27’的子节点，发现右子节点‘65’大，将结点‘27’与结点‘65’交换：

此时结点‘27’的左右子树都为大堆，对结点‘27’进行向下调整，比较结点‘27’的子节点，发现左子节点‘34’大，将结点‘34’与结点‘27’交换：

 

这样就完成了，在左右子树已经是大堆的前提下，使得整个数组成为了大堆：

 

4.2建堆

前面根据向下调整算法有一个前提就是，左右子树必须是堆，那如何将左右子树变成堆呢？

建堆：从最后一个结点的父结点往前使用向下调整算法。

有这样一个数组：arr[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37}

先找到最后一个结点‘37’的父结点‘28’，进行向下调整：

往前找到结点‘18’进行向下调整：

往前找到结点‘19’进行向下调整：

 

往前找到结点‘15’进行向下调整，由与是从后向前调整，使得整个结点‘15’的左右子树均为大堆，满足向下调整算法的前提：

 

往前找到结点‘27’进行向下调整，由与是从后向前调整，使得整个结点‘27’的左右子树均为大堆，满足向下调整算法的前提：

通过从后向前进行向下调整，成功让无序的数组变成了大堆：

 

以上可以看出只要从最后一个结点的父结点往前使用向下调整算法就能总是满足，左右子数必须是堆的前提，这样就实现了建堆的整个过程。

---

5.堆实现

5.1堆结构

typedef int HeapDataType;
 
typedef struct Heap {
	HeapDataType* data;
	int size;
	int capacity;
}Heap;

Heap:堆结构组成

HeapDataType:指链表中每个结点存储的数据类型，只需要改动typedef int HeapDataType 中的int就能该变节点内存放的数据类型。

data:HeapDataType类型的数组指针。

capacity：数组可存放大小。

size：数组已存放大小。

5.2数组功能实现

文件：”Heap.c“

5.2.1向下调整算法

void AdjustDown(Heap* ph, int parent)				//向下调整算法
{
	assert(ph);
	int	child = parent * 2 + 1;
	while (child < ph->size)
	{
		if (child + 1 < ph->size && ph->data[child + 1] > ph->data[child])	
		{
			child++;		//找出左右孩子中大的那个
		}
 
		if (ph->data[child] > ph->data[parent])			//孩子大于父亲就交换
		{
			Swap(&ph->data[child], &ph->data[parent]);
			parent = child;								//孩子成为父亲
			child = parent * 2 + 1;						//继续找孩子
		}
		else
		{
			break;										//孩子不大于父亲结束调整
		}
	}
}

5.2.2建堆

void BuildHeap(Heap* ph)							//建堆
{
	assert(ph);
	for (int i = (ph->size - 1 - 1) / 2; i >= 0; i--)	
	{
		AdjustDown(ph, i);							//从最后一个父亲想前调整
	}
}

5.2.3向上调整算法

void AdjustUp(Heap* ph, int child)					//向上调整算法
{
	assert(ph);
	assert(child < ph->size);
	int parent = (child - 1) / 2;					//找出父亲
	while (child > parent)
	{
		if (ph->data[child] > ph->data[parent])		//孩子大于父亲交换
		{
			Swap(&ph->data[child], &ph->data[parent]);
			child = parent;							//父亲成为孩子
			parent = (child - 1) / 2;				//继续找父亲
		}
		else
		{
			break;									//孩子不大于父亲结束调整
		}
	}
 
}

5.2.4堆初始（给一个数组建成堆）

void HeapInit(Heap* ph, HeapDataType* str, int size)	//堆初始
{
	assert(ph);
	assert(str);
	//给定数组建成堆，并初始
	HeapDataType* DataSpace;
	DataSpace = (HeapDataType*)malloc(sizeof(HeapDataType) * size);	//开辟给定数组相等空间
	assert(DataSpace);
	memcpy(DataSpace, str, size*sizeof(HeapDataType));				//将数组内容拷贝进堆
	ph->data = DataSpace;											
	ph->size = size;												//堆初始大小等于数组大小
	ph->capacity = size;
 
	//建堆
	BuildHeap(ph);												
}

5.2.5堆打印

void HeapPrint(Heap* ph)								//堆打印
{
	assert(ph);
	for (int i = 0; i < ph->size; i++)
	{
		printf("%d ", ph->data[i]);
	}
	printf("\n");
}

5.2.6入堆

void HeapPush(Heap* ph, HeapDataType x)					//入堆
{
	assert(ph);
	if (ph->capacity == ph->size)				//判段堆是否已满
	{
		HeapDataType* newspace;
		newspace = (HeapDataType*)realloc(ph->data, sizeof(HeapDataType) * (ph->size)*2);
		assert(newspace);
		ph->data = newspace;
		ph->capacity = ph->capacity * 2;
	}
	ph->data[ph->size] = x;
	ph->size++;
 
	AdjustUp(ph,ph->size - 1);					//将入堆数据放到堆最后，进行向上调整
}

5.2.7出堆

void HeapPop(Heap* ph)									//出堆
{
	//出堆头数据
	assert(ph);
	Swap(&ph->data[0], &ph->data[ph->size - 1]);		//将头尾数据交换
	ph->size--;											//堆大小减1
	AdjustDown(ph, 0);									//堆剩余内容向下调整
}

5.2.8堆顶数据

HeapDataType HeapTop(Heap* ph)							//堆顶数据
{
	assert(ph);
	assert(ph->data);
	return ph->data[0];
}

5.2.9堆大小

int HeapSize(Heap* ph)									//堆大小
{
	assert(ph);
	return ph->size;
}

5.2.10判空

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

5.2.11堆销毁

void HeapDestroy(Heap* ph)								//堆销毁
{
	assert(ph);
	free(ph->data);							//释放堆空间
	ph->data = NULL;						//堆空间指针指空
	ph->size = ph->capacity = 0;			//堆大小堆容量置零
}

5.3堆头文件

文件：”Heap.h“

#pragma once
 
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#include"stdbool.h"
 
//大堆
 
typedef int HeapDataType;
 
typedef struct Heap {
	HeapDataType* data;
	int size;
	int capacity;
}Heap;
 
//堆操作
void Swap(HeapDataType* a, HeapDataType* b);
void AdjustUp(HeapDataType* Heap, int parent);
void AdjustDown(Heap* ph);
void BuildHeap(HeapDataType* Heap, int size);
 
 
//堆接口
void HeapInit(Heap* ph, HeapDataType* str, int size);	//堆初始
void HeapPrint(Heap* ph);								//堆打印
void HeapPush(Heap* ph,HeapDataType x);					//入堆
void HeapPop(Heap* ph);									//出堆
HeapDataType HeapTop(Heap* ph);							//堆顶数据
int HeapSize(Heap* ph);									//堆大小
bool HeapEmpty(Heap* ph);								//判空
void HeapDestroy(Heap* ph);								//堆销毁

5.4堆功能测试

文件：”test.c“

//大堆
#include"Heap.h"
 
void test1()
{
	HeapDataType str[] = { 27,15,19,18,28,34,65,49,25,37 };
	Heap heap;
	int strsize = sizeof(str) / sizeof(str[0]);
	HeapInit(&heap, str, strsize);			//堆初始测试
	HeapPrint(&heap);						//堆打印测试
 
	HeapPush(&heap, 88);					//入堆测试
	HeapPrint(&heap);
 
	while (!HeapEmpty(&heap))				//判空测试
	{
		printf("top:%d\n", HeapTop(&heap));	//堆顶数据测试
		HeapPop(&heap);						//出堆测试
		HeapPrint(&heap);		
	}
 
	HeapPush(&heap, 88);					//出空再入测试
	//HeapPrint(&heap);
 
	HeapDestroy(&heap);						//堆销毁测试
 
}
 
int main()
{
	test1();
	return 0;
}

---

✨写在最后

⏱笔记时间：2022_01_10

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/905831