[数据结构与算法]数据结构——堆

什么是堆

把所有的元素按照完全二叉树的形式储存在一维数组中，如果该二叉树满足父节点小于等于子节点，叫做小堆；如果该二叉树满足父节点大于等于子节点，叫做大堆。

堆的实现

堆类型的创建

堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。
堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数。

typedef int HPDataType;

typedef struct heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Heap;

堆的初始化

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->arr = NULL;
	hp->size = hp->capacity = 0;
}

堆的向上调整算法和向下调整算法

向上调整算法

给我的节点当做子节点，然后找到父节点，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点到根节点就停止比较，这时就已经调整好一次了。
下面的这个例子调整成的是小堆

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType c = *a;
	*a = *b;
	*b = c;
}

void adjustup(Heap* hp, int child)
{
	int father = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->arr[child] < hp->arr[father])
		{
			swap(&(hp->arr[child]), &(hp->arr[father]));
			child = father;
			father = (child - 1) / 2;
		}	
		else
			break;
	}
}

向下调整算法

给我的节点当做父节点，然后找到子节点(这个节点为左孩子，我们需要找到这两个孩子中较大的或者较小的当作子节点)，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点超过节点个数的时候就停止比较，这时就已经调整好一次了。

void adjustdown(Heap* hp, int father)
{
	int child = 2 * father + 1;
	while (child < hp->size)
	{
	//因为这里有child+1，所以要注意边界问题
		if (child < hp->size-1&&hp->arr[child] > hp->arr[child + 1])
			child++;
		if (hp->arr[child] < hp->arr[father])
		{
			swap(&(hp->arr[child]), &(hp->arr[father]));
			father=child;
			child = 2 * father + 1;
		}
		else
			break;
	}
}

堆的插入

为了不破坏堆的性质，我们在堆的最后进行插入(想一下其实在最后进行插入就不需要调整其他的元素了)
插入完成之后，我们需要调整成堆的形式。这里我们用堆的向上调整算法。进行调整.

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* newarr = (HPDataType*)realloc(hp->arr, newcapcity * sizeof(HPDateType));
		if (newarr == NULL)
			exit(-1);
		hp->arr = newarr;
		hp->capacity = newcapcity;
	}
	hp->arr[hp->size] = x;
	hp->size++;

	//向上调整
	adjustup(hp,hp->size-1);
}

堆的删除

对于删除堆头的数据，我们是把堆尾的数据覆盖头，元素个数减1，然后用堆的向下调整算法，进一步调整成堆。

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size);
	
	swap(&(hp->arr[0]), &(hp->arr[hp->size-1]));
	hp->size--;
	//向下调整
	adjustdown(hp,0);
}

堆的销毁

void HeapDestrop(Heap* hp)
{
	assert(hp);
	free(hp->arr);
	hp->size = hp->capacity = 0;
}

打印堆

void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->arr[i]);
	}
	printf("\n");
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系