数据结构——二叉树的顺序结构及实现（堆）

头删代码;

void HeapPop(HP* php)
{
	assert(php);
	Swap(php->a, &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

 剩余函数较简单，相信大家一看就明白了

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

注：这里默认是小堆，如果对头文件BIGHEAP的宏进行解引用可实现大堆

#pragma once
#include
#include
#include
#include
#include
//#define BIGHEAP//若大堆，则解除注释,否则加注释
#define SIGN <
#ifdef BIGHEAP
#undef SIGN
#define SIGN >
#endif

// 小堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPrint(HP* php);

// 插入x以后，保持他依旧是(大/小)堆
void HeapPush(HP* php, HPDataType x);

// 删除堆顶的数据。

(最小/最大)
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);

#include"Heap.h"

void Swap(HPDataType* pa, HPDataType* pb)
{
	assert(pa && pb);
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void HeapDestroy(HP* php)
{
	assert(php);
	assert(php->a);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void AdjustUp(HPDataType* a, size_t child)
{
	assert(a);
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] SIGN a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}
void AdjustDown(HPDataType*a,size_t size,size_t root)
{
	assert(a);
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1a, &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

#include"Heap.h"
int main()
{
	HP h;
	HeapInit(&h);
	HeapPush(&h, 2);
	HeapPush(&h, 5);
	HeapPush(&h, 7);
	HeapPush(&h, 1);
	HeapPush(&h, 4);
	HeapPrint(&h);
	HeapPop(&h);
	HeapPrint(&h);
	printf("%d", HeapTop(&h));
}

堆排序即使用堆的思想进行排序，总共分为两个步骤：

        1.建堆

        2.利用堆删除的思想进行排序

我们先上个简单的版本，用刚刚实现的堆来完成堆排序。

整体思路为：

        1.首先新建一个堆，遍历整个数组，将所有元素Push到堆中。

        2.此时如果是小堆，那堆首元素一定最小，我们就将这个元素存入数组，然后把这个元素从堆中头删掉。

        3.循环第二个动作，直至将堆清空。

代码：

void HeapSort(int* a,size_t size)
{
	HP hp;
	HeapInit(&hp);
	//建堆
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//堆删除
	for (int i = 0; i < size; i++)
	{
		a[i] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

我们看一它的时间复杂度：

循环遍历是O(N)；

Push *** 作最坏情况走的是树的高度步，假设每次都是n个节点，则高度就是logN，也就是O(logN）；

整个建堆过程就是O(N*logN)；

堆删除与建堆基本形同，也是O(N*logN)；

整个堆排序的时间复杂度也就是O(N*logN)。

再来看一下空间复杂度：
我们额外建堆，就需要一个与数组大小相等的数组，空间复杂度也就是O(N);

时间复杂度是O(N*logN)，对于一个堆排序来说就是标准，但空间复杂度的O(N)完全没有必要，我们是否可以在原数组上进行排序呢？而且排个序还要写个堆，未免有些小蠢。

那么我们来看看下面的升级版。

原则与上面基本相同，还是建堆、删堆，只不过我们现在要脱离建堆删掉等封装好的函数，直接用算法在数组上原地 *** 作。

建堆：

这时，然我们一起回忆一下向上调整，和向下调整这两个神奇的算法。

向上调整：从堆尾插入一个元素，只要这个元素经历过一次向上调整算法，他就能找到自己该去的位置，从而有形成一个堆。

向下调整：当堆顶节点的左右子树都是堆，但政整棵二叉树不是堆，这时通过对堆顶元素向下调整就可以形成一个堆。

有了这两个前提，我们再看看怎么原地建堆：

1.向上调整建堆：

• 对数组的第二个元素进行向上调整，此时最前面的两个元素就形成了一个堆。
  

  
  

• 然后对第三个元素进行向上调整，这时前三个元素又形成一个堆，
• 再进行第3，4，5个元素向上调整，直至调整完尾元素，此时就原地建好了一个堆。
  

  
  

2.向下调整建堆：

相对上面有点难想，上个图先：

 这里我们从下面开始，但不是最后一个元素（下面没东西也没法往下调），我们从元素8开始进行向下调，调整之后，这部分就成了堆：

然后再是对7向下调：

以此逻辑直至整棵树成堆：

3.时间复杂度比较：

 大家可能觉得这两种方式建堆