【数据结构】_堆的实现

目录

1. 堆的实现

1.1 Heap.h

1.2 Heap.c

1.3 Test_Heap.c

专栏前文中，已经介绍了入堆及向上调整算法，出堆及向下调整算法，详情见下文：

【数据结构】_堆的结构及向上、向下调整算法-CSDN博客文章浏览阅读352次，点赞6次，收藏10次。实际对于整除运算parent = (child - 1) / 2，parent并不会小于0，但当parent=0时，若a[parent] > a[child]，则再次进行child与parent的更新，使得parent与child均为0。当parent=0时，若若a[parent] > a[child]，则再次进行child与parent的更新，使得child更新为0，下次则无法进入while循环；，删除最后一个结点后，再逐层调整父结点与子结点的大小关系，使其满足小根堆特性；（1）堆是完全二叉树；https://blog.csdn.net/m0_63299495/article/details/145515724https://blog.csdn.net/m0_63299495/article/details/145515724https://blog.csdn.net/m0_63299495/article/details/145515724

以小根堆为例：

1. Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HPInit(HP* php); 
void HPDestory(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
void HPPrint(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void Swap(HPDataType* px, HPDataType* py);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);

2. Heap.c

#include"Heap.h"
void HPInit(HP* php) {
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HPDestory(HP* php) {
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void Swap(HPDataType* px, HPDataType* py) {
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
// 向上调整
void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child> 0) {
		// 父结点值大于子结点值：交换并更新parent和child
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			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 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp== 0) {
			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;
	// child=n表示已经遍历到最后的叶结点
	while (child < n) {
		// 确定左右孩子中更小的
		if (child+1<n && a[child] > a[child + 1]) {
			child++;
		}
		// 若子结点小于父结点，则交换并更新parent和child
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 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);
}
void HPPrint(HP* php) {
	for (int i = 0; i < php->size; i++) {
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
HPDataType HPTop(HP* php) {
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
bool HPEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}

3. Test_Heap.c

使用HPPush方法构建小根堆：

#include"Heap.h"
void TestHeap1() {
	int a[] = { 4,2,8,1,5,6,9,7 };
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
		HPPush(&hp, a[i]);
	}
	HPPrint(&hp);
	HPDestory(&hp);
}
int main() {
	TestHeap1();
	return 0;
}

运行结果如下：

注：大根堆与小根堆的转换：