堆的数组实现

前言

本次博客来讲解一下堆的数组实现，好吧还是会结合图例，让大家理解

堆的定义

什么是堆？

堆是一颗完全二叉树。它的性质是父节点一定大于或者一定小于子节点

每一个结点都要满足这个性质就是堆

堆的特性是堆顶的数据一定是最大或最小，最大为大堆，最小为小堆

看图

那我们如何实现堆呢？

我们可以注意堆是一个完全二叉树，我们可以使用一个数组来模拟完全二叉树

那么如何使用数组实现完全二叉树

使用数组实现完全二叉树

OK，首先我们可以通过数组下标，来确定节点，只要能够得到父子关系就可以遍历整个完全二叉树，看图吧

OK，那么咱么可不可以实现一下前序遍历呢

使用递归和非递归

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define N 10
//适用于满二叉树和完全二叉树
typedef struct BianryTree {
	int a[N];
}BT;
void InitBinaryTree(BT* bt,int cursize)
{
	if (cursize >= N)
		return;
	bt->a[cursize] = cursize;
	InitBinaryTree(bt,cursize*2+1);
	InitBinaryTree(bt,cursize*2+2);
}
void TraversalTree(BT* bt, int cursize)
{
	if (cursize >= N)
		return;
	printf("%d ", bt->a[cursize]);
	TraversalTree(bt, cursize * 2 + 1);
	TraversalTree(bt, cursize * 2 + 2);
}
int main()
{
	BT* bt = (BT*)malloc(sizeof(BT));
	InitBinaryTree(bt,0);
	TraversalTree(bt, 0);
	return 0;
}

上面是前序遍历属于递归遍历

接下来看非递归遍历，其实可以

void TraversalTree(BT* bt, int cursize)
{
	while (cursize < N)
		printf("%d ", bt[cursize++]);
}

只需改一改就好，这里相当于层序遍历

那么使用数组去实现完全二叉树是可行的

数组实现堆

我们先看看堆有哪些接口，然后一一实现

看一看头文件吧

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HpDatatype;
typedef struct Heap {
	HpDatatype* a;
	int capacity;
	int size;
}HP;
void IintHeap(HP* hp);
void PushHeap(HP* hp, HpDatatype x);
void PopHeap(HP* hp);
HpDatatype TopHeap(HP* hp);
void DestroyHeap(HP* hp);
bool EmptyHeap(HP* hp);
int SizeHeap(HP* hp);

先实现几个简单的初始化，没什么好说的

void IintHeap(HP* hp)
{
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

返回堆大小，也没有什么好说的

int SizeHeap(HP* hp)
{
	assert(hp);
	return hp->size;
}

返回堆顶

HpDatatype TopHeap(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}

判空

bool EmptyHeap(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

销毁堆

void DestroyHeap(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = 0;
	hp->size = 0;
}

插入数据

void PushHeap(HP* hp, HpDatatype x)
{
	assert(hp);
	//检查容量
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HpDatatype* temp = (HpDatatype*)realloc(hp->a, sizeof(HpDatatype) * newcapacity);
		if (temp == NULL)
		{
			printf("realloc fail\n");
			return;
		}
		else
		{
			hp->a=temp;
			hp->capacity = newcapacity;
		}
	}
	//向上调整法
	hp->a[hp->size++] = x;
	AdjustUp(hp->a,hp->size-1);
}

这个代码的逻辑是，每插入一个数据，对该数据进行向上调整法

那么向上调整法可以确保，每插入一个数据，该数组保持为堆

那么现在我们画图来理解什么是向上调整法

OK，下面是向上调整法

void AdjustUp(HpDatatype* a, int child)
{
	//这里的向上调整法是调整它的祖先
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])
		{
			int temp = a[child];
			a[child] = a[parent];
			a[parent] = temp;
			child = parent;
		}
		else
		{
			break;
		}
	}
}

删除一个数据

void PopHeap(HP* hp)
{
	assert(hp);
	assert(hp->a > 0);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	//向下调整法
	AdjustDown(hp->a, 0, hp->size);
	hp->size--;
}

我们要删除的是堆顶的数据

所以让第一个数据与最后一个数据交换，size--

此时，第一个节点的左子树和右子树都是堆，我们只要再调整一下根节点即可

这种调整叫做向下调整法

这里就不画图了，有点麻烦

直接看代码吧

void AdjustDown(HpDatatype* a, int start, int end)
{
	int parent = start;
	//假设法，假设左孩子更接近目的
	int child = parent * 2 + 1;
	end = end - 1;
	while (child <end)
	{
		if (child + 1 < end && a[child + 1] < a[child])
			child++;
		if (a[parent] > a[child])
		{
			swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

这里的逻辑就是，先使用假设法让child唯一

然后，比对a[child]和a[parent]的大小满足条件则交换

大堆 a[child]>a[parent] 小堆 a[child]<a[parent]

如果不满足条件，直接结束.