一，堆的实现

1.结构

//堆的底层是一个完全二叉树，所以说我们用数组实现是不会有空间的浪费的。
//物理上是一个数组，但是逻辑上可以把他想象成一颗二叉树。
typedef ?int HPDataType;
typedef struct Heap
{
?? ?HPDataType* a;
?? ?size_t size;
?? ?size_t capacity;
}Heap;

2，函数接口

void swap(HPDataType* pa, HPDataType* pb);
void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
void HeapPrint(Heap* php);

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

// 删除堆顶的数据。(最小/最大)
void HeapPop(Heap* php);
bool HeapEmpty(Heap* php);
size_t HeapSize(Heap* php);
HPDataType HeapTop(Heap* php);
//向上调整算法
void Adjustup(HPDataType* a,size_t child);
//向下调整算法。
void Adjustdown(HPDataType* a, size_t size,size_t root);

3，接口实现

void swap(HPDataType* pa, HPDataType* pb)
{
?? ?HPDataType tmp = *pa;
?? ?*pa = *pb;
?? ?*pb = tmp;
}
void Adjustup(HPDataType* a, size_t child)
{
?? ?//假设我们这里搞一个小堆。大堆的话也是对应的。
?? ?assert(a);
?? ?size_t parent = (child - 1) / 2;
?? ?while (child > 0)
?? ?{
?? ??? ?//if (a[child] > a[parent]) ?大堆
?? ??? ??? ?if (a[child] < a[parent]) ? //小堆
?? ??? ?{
?? ??? ??? ?swap(&a[child], &a[parent]);
?? ??? ??? ?child = parent;
?? ??? ??? ?parent = (child - 1) / 2;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?//走到这里那就是已经是堆了，可以提前结束了。
?? ??? ??? ?break;
?? ??? ?}
?? ?}
}

void Adjustdown(HPDataType* a, size_t size, size_t root)
{
?? ?assert(a);
?? ?//假设我们这里还是建小堆
?? ?size_t parant = root;
?? ?size_t child = parant*2+1; ?//这里默认是左孩子，要算有孩子加一就是了。
?? ?while (child<size)
?? ?{
?? ? ? ?//选出左右孩子中的较小的那个
?? ??? ?if (child+1<size && a[child + 1] < a[child])
?? ??? ?{
?? ??? ??? ?child++;
?? ??? ?}
?? ??? ?//小堆，大堆相反就行。
?? ??? ?if (a[child] < a[parant])
?? ??? ?{
?? ??? ??? ?swap(&a[child], &a[parant]);
?? ??? ??? ?parant = child;
?? ??? ??? ?child = parant*2+1;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?//已经是堆了，不需要调整了，提前结束。
?? ??? ??? ?break;
?? ??? ?}
?? ?}
}
void HeapInit(Heap* php)
{
?? ?assert(php); ?//给我传的结构体一定不能为空吧。
?? ?php->a = NULL;
?? ?php->capacity = php->size = 0;
}
void HeapDestroy(Heap* php)
{
?? ?assert(php);
?? ?free(php->a);
?? ?php->a = NULL;
?? ?php->capacity = php->size = 0;
?? ?//这里不可以释放php。
}
void HeapPrint(Heap* php)
{
?? ?assert(php);
?? ?for (size_t i = 0; i < php->size; i++)
?? ??? ?printf("%d ", php->a[i]);
?? ? ? ?printf("\n");
}

// 插入x以后，保持他依旧是(大/小)堆
void HeapPush(Heap* php, HPDataType x)
{
?? ?assert(php);
?? ?if (php->capacity == php->size)
?? ?{
?? ??? ?//扩容。
?? ??? ?int nwecapacity = php->capacity == 0 ? 4 : php->capacity * 2;
?? ??? ?HPDataType* tmp = realloc(php->a, nwecapacity * sizeof(HPDataType));
?? ??? ?//检查开空间是否成功。
?? ??? ?if (tmp == NULL)
?? ??? ?{
?? ??? ??? ?printf("realloc ?fail\n");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ??? ?php->a = tmp;
?? ??? ??? ?php->capacity = nwecapacity; ? //容易忘记
?? ?}

?? ?php->a[php->size++] = x; ?//在最后插入。
?? ?//插入之后堆的结构就可能不能保持了，需要向上调整，因为我们是在最后插入。
?? ?Adjustup(php->a, php->size - 1); ?//第二个参数传的是从那个位置开始调整。
}

// 删除堆顶的数据。(最小/最大)
void HeapPop(Heap* php)
{
?? ?assert(php);
?? ?assert(php->size > 0);
?? ?swap(&php->a[0], &php->a[php->size - 1]);
?? ?php->size--;
?? ?//Adjustdown(php->a, php->size - 1, 0); ? size前面已经减过了，不需要在减了。
?? ?Adjustdown(php->a, php->size, 0);
}
bool HeapEmpty(Heap* php)
{
?? ?assert(php);
?? ?return php->size == 0;
}
size_t HeapSize(Heap* php)
{
?? ?assert(php);
?? ?return php->size;
}
HPDataType HeapTop(Heap* php)
{
?? ?assert(php);
?? ?assert(php->size > 0);
?? ?return php->a[0];
}

4，代码链接

data structure: 数据解构练习 - Gitee.com

二，堆排序的实现

本质其实是一种选择排序，排降序建小堆，排升序，建大堆。

选出一个数之后，在不破换结构的基础上把他放到该有的位置

上。

1.建堆

建堆 ? ?向上调整建堆 ?或 ?向下调整建堆。 ? 比较时间复杂度发现向下调整是更优秀的。所以我们用向下调整来建堆，向下调整算法，向上调整算法在堆的实现里面都是有的，就是那个Adjustup（）和Adjustdowm（）看函数名字因该就可以区分那个是那个了。

for (int i = (n - 2) / 2; i >=0; i--)
	{
		Adjustdown(a,n, i);  //第二个参数是数据个数，限制了最多向下到哪里。
	}

2，选择排序思想，只不过是用堆来选择。

	//这里其实本质上是用来选择排序的思想，选出一个数，放到他该有的位置上。
	size_t end = n - 1;
	while (end > 0)
	{
		swap(&a[end], &a[0]);
		Adjustdown(a, end, 0);
		end--;   //--之后代表最后一个元素的位置，没减之前代表需要调整的元素个数。
	}

选好一个数之后就放到该有的位置上，然后调整剩下的，使之还是一个堆，用向下调整算法去调整。