[数据结构与算法]堆的基础详解

堆的概念及性质

?总之一点就是父亲结点总是比孩子结点大的叫大堆，总是比孩子结点小的，叫小堆。结构如图所示。

?

?堆的实现

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

?

? 如图所示，如果我们先将数组不管大小先按二叉树排序，然后在调整，向下调整。于是得到了最后的小堆。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDtaType;

typedef struct Heap
{
	HPDtaType* a;
	int size;
	int capacity;
}HP;

创建结构体

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void AdjustUp(HPDtaType* a, int chlid)
{
	int parent = 0;
	parent = (chlid - 1) / 2;
	while (chlid)//当chlid为零时，循环停止
	{
		if (a[parent] < a[chlid])//当孩子结点大于双亲结点时，就进行交换，
		{
			HPDtaType tmp = a[chlid];
			a[chlid] = a[parent];
			a[parent] = tmp;
			chlid = parent;
			parent = (chlid - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(HPDtaType* a,int n, int partent)
{
	int chlid = 0;
	chlid = partent * 2 + 1;
	while (chlid < n)
	{
		if (a[chlid + 1] > a[chlid])
		{
			chlid++;
		}
		if (a[chlid] < a[partent])
		{
			Swap(&a[chlid], &a[partent]);
			partent = chlid;
			chlid = partent;
		}
		else
		{
			break;
		}
	}
}

void Swap(HPDtaType*px, HPDtaType*py)
{
	HPDtaType tmp = *px;
	*px = *py;
	*py = tmp;
}
void HeapInit(HP*hp)//堆的初始化
{
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
void HeapDestroy(HP*hp)//堆的销毁
{
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
void HeapPush(HP*hp, HPDtaType x)//往堆里压数据
{
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDtaType* tmp = realloc(hp->a, sizeof(HPDtaType)*newcapacity);//如果数组的内存不够，就进行扩容
		if (tmp == NULL)
		{
			printf("realloc fail\n");//如果realloc失败就提示提示并退出
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	AdjustUp(hp->a, hp->size);
	hp->size++;
}
void HeapPrint(HP*hp)//打印数组
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

各种对的接口函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void test()
{
	int a[] = { 10, 15, 22, 14, 53, 22, 50, 70, 75 };
	int sz = sizeof(a) / sizeof(a[1]);
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);



	HeapDestroy(&hp);

}
int main()
{
	test();

	return 0;
}

最后的测试代码

?最后的结果