您的位置: 首页  >  文章  >  数据结构---堆的相关操作

数据结构---堆的相关操作

分类: 文章 • 2023-11-18 08:09:58

数据结构—堆

堆的概念

  • 如果有一个关键码的集合K = { k0，k1， k2，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，
  • 并满足： Ki <= K2 * i+1 且 Ki <= K2 * i +2 (Ki >= K2 * i + 1 且 Ki >= K2 * i + 2) i = 0，1，2…，则称为小堆(或大堆)。
    数据结构---堆的相关操作
  • 小堆(大堆)中：任一结点的关键码均小于(大于)等于它的左右孩子的关键 码，位于堆顶结点的关键码最小(最大)，从根节点到每个结点的路径上数组元素组成的序列都是递增(递减)的。
  • 堆存储在下标为0开始的数组中，因此在堆中给定下标为i的结点时：
    • 如果i=0，结点i是根节点，没有双亲节点；否则结点i的双亲结点为 结点(i-1)/2
    • 如果2 * i + 1 <= n - 1，则结点i的左孩子为结点2 * i + 1，否则结 点i无左孩子
    • 如果2 * i + 2 <= n - 1，则结点i的右孩子为结点2 * i + 2，否则结 点i无右孩子

堆的创建

数据结构---堆的相关操作

  • 将二叉树调整为最小堆的原理：
    • 从最后一个非叶子结点开始调整，一直到根节点为止，将每个结点及其子 树调整到满足小堆的性质即可
      数据结构---堆的相关操作

堆的插入&删除

  • 插入
  • 堆的插入：在已经建成的最小堆的后面插入新元素，插入之后，当树 中结点不满足堆的性质时，就需要对堆进行重新调整
    数据结构---堆的相关操作
  • 删除
  • 堆的删除：删除时每次删除堆顶元素
    数据结构---堆的相关操作

代码实现

  • 定义堆的数据结构
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* _hp;
	int _capacity;
	int _size;
	PCompare _compare;
}Heap;
  • 这时由用户选择建立大堆还是小堆的函数，这块用到了函数指针的概念，不熟悉的自行看看c语言。
typedef int(*PCompare)(HPDataType left, HPDataType right);

int Less(HPDataType left, HPDataType right)
{
	return left < right;
}

int Greater(HPDataType left, HPDataType right)
{
	return left > right;
}
  • 创建堆的函数：先将数组中的元素导入到结构体中，然后在用向下调整法使他成为堆。
void CreateHeap(Heap* hp, int* array, int size, PCompare compare)
{
	assert(hp);
	int root = ((size - 2) >> 1);
	hp->_hp = (HPDataType*)malloc(size*sizeof(HPDataType));
	if (!hp->_hp)
	{
		assert(0);
		return;
	}
	hp->_capacity = 9;

	memcpy(hp->_hp, array, size*sizeof(HPDataType));
	hp->_size = size;
	hp->_compare = compare;

	for (; root >= 0; root--)
		AdjustDown(hp, root);
}
  • 向下调整法：拿到传过来的节点，找到他的孩子节点。进入循环中，设置判断得到这个节点的左孩子或者右孩子（由条件大堆小堆决定）。然后交换这个母亲节点和孩子节点，继续往下调整。
void AdjustDown(Heap* hp, int parent)
{
	assert(hp);
	int child = (parent << 1) + 1;
	while (child < hp->_size)
	{
		if (child + 1 < hp->_size  && hp->_compare(hp->_hp[child + 1], hp->_hp[child]))
			child += 1;

		if (hp->_compare(hp->_hp[child], hp->_hp[parent]))
		{
			Swap(&hp->_hp[child], &hp->_hp[parent]);
			parent = child;
			child = (parent << 1) + 1;
		}
		else
			return;
	}
}
  • 检查开辟的内存够不够，不够的话还需要重新开辟。
void CheckCapacity(Heap* hp)
{
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		int new_capacity = (hp->_capacity << 1) + 3;
		HPDataType* pTemp = (HPDataType*)malloc(new_capacity*sizeof(HPDataType));
		if (!pTemp)
		{
			assert(0);
			return;
		}
		if (hp->_hp)
		{
			for (int i = 0; i < hp->_size; i++)
			pTemp[i] = hp->_hp[i];

			free(hp->_hp);
		}
		
		hp->_hp = pTemp;
		hp->_capacity = new_capacity;
	}
}
  • 向上调整法：用于插入函数中，当插入完成后，需要检查是否这个节点是否满足堆的性质。得到这个插入的新节点后，找到这个新节点的母亲节点，然后判断是否需要交换。如果交换之后，就需要往上遍历，看看交换后是否满足堆的性质。
void AdjustUp(Heap* hp, int child)
{
	assert(hp);
	int parent = ((child - 1) >> 1);
	while (child)
	{
		if (hp->_compare(hp->_hp[child], hp->_hp[parent]))
		{
			Swap(&hp->_hp[child], &hp->_hp[parent]);
			child = parent;
			parent = ((child - 1) >> 1);
		}
		else
			return;
	}
}
  • 向堆中插入新节点：插入节点之前需要判断这个堆的容量是否足够，插入完毕之后，进行向上调整。
void InsertHeap(Heap* hp, HPDataType data)
{
	assert(hp);
	CheckCapacity(hp);
	hp->_hp[hp->_size++] = data;

	AdjustUp(hp, hp->_size - 1);
}
  • 判断堆是否为空
int EmptyHeap(Heap* hp)
{
	return 0 == hp->_size;
}
  • 获取堆的元素个数
int SizeHeap(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
  • 获取堆顶元素
HPDataType TopHeap(Heap* hp)
{
	assert(hp);
	return hp->_hp[0];
}

最后附上所有代码，包括调试代码

#pragma once
#include <assert.h>
#include <malloc.h>
#include <string.h>

typedef int(*PCompare)(HPDataType left, HPDataType right);

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* _hp;
	int _capacity;
	int _size;
	PCompare _compare;
}Heap;

int Less(HPDataType left, HPDataType right)
{
	return left < right;
}


int Greater(HPDataType left, HPDataType right)
{
	return left > right;
}

void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

void AdjustDown(Heap* hp, int parent)
{
	assert(hp);
	int child = (parent << 1) + 1;
	while (child < hp->_size)
	{
		if (child + 1 < hp->_size  && hp->_compare(hp->_hp[child + 1], hp->_hp[child]))
			child += 1;

		if (hp->_compare(hp->_hp[child], hp->_hp[parent]))
		{
			Swap(&hp->_hp[child], &hp->_hp[parent]);
			parent = child;
			child = (parent << 1) + 1;
		}
		else
			return;
	}
}

void CreateHeap(Heap* hp, int* array, int size, PCompare compare)
{
	assert(hp);
	int root = ((size - 2) >> 1);
	hp->_hp = (HPDataType*)malloc(size*sizeof(HPDataType));
	if (!hp->_hp)
	{
		assert(0);
		return;
	}
	hp->_capacity = 9;

	memcpy(hp->_hp, array, size*sizeof(HPDataType));
	hp->_size = size;
	hp->_compare = compare;

	for (; root >= 0; root--)
		AdjustDown(hp, root);
}

void CheckCapacity(Heap* hp)
{
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		int new_capacity = (hp->_capacity << 1) + 3;
		HPDataType* pTemp = (HPDataType*)malloc(new_capacity*sizeof(HPDataType));
		if (!pTemp)
		{
			assert(0);
			return;
		}
		if (hp->_hp)
		{
			for (int i = 0; i < hp->_size; i++)
			pTemp[i] = hp->_hp[i];

			free(hp->_hp);
		}
		
		hp->_hp = pTemp;
		hp->_capacity = new_capacity;
	}
}

void AdjustUp(Heap* hp, int child)
{
	assert(hp);
	int parent = ((child - 1) >> 1);
	while (child)
	{
		if (hp->_compare(hp->_hp[child], hp->_hp[parent]))
		{
			Swap(&hp->_hp[child], &hp->_hp[parent]);
			child = parent;
			parent = ((child - 1) >> 1);
		}
		else
			return;
	}
}


void InsertHeap(Heap* hp, HPDataType data)
{
	assert(hp);
	CheckCapacity(hp);
	hp->_hp[hp->_size++] = data;

	AdjustUp(hp, hp->_size - 1);
}

int EmptyHeap(Heap* hp)
{
	return 0 == hp->_size;
}


void RemoveHeap(Heap* hp)
{
	assert(hp);
	if (EmptyHeap(hp))
		return;
	Swap(&hp->_hp[0], &hp->_hp[hp->_size - 1]);
	hp->_size--;
	AdjustDown(hp, 0);
}

int SizeHeap(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

HPDataType TopHeap(Heap* hp)
{
	assert(hp);
	return hp->_hp[0];
}

void TestHeap()
{
	int arr[] = {53, 17, 78, 9, 45, 65, 87, 23, 31};
	Heap hp;
	CreateHeap(&hp, arr, sizeof(arr) / sizeof(arr[0]), Greater);
	InsertHeap(&hp, 10);
	RemoveHeap(&hp);
}

如果发现问题，欢迎下方留言讨论

相关推荐