1.堆

堆的性质：

创建堆

向上调整建堆

向下调整建堆

堆的插入

向上调整算法

数组一个个循环插入时边插入边成堆，当插入新的元素时向上调整成新的堆

使用向上调整算法，每次孩子与父亲相比较，当孩子大于或小于父亲时进行交换，改变孩子的下标，再次进行判断然后交换，知道孩子的下标为0

当已经成大堆或者小堆后想删元素，最好的办法是把堆的第一个元素与最后一个进行交换，当交换完成，堆中最大或最小的元素就到了最后一个结点，减小下标进行删除，此时堆顶的左右子树为大堆或者小堆，用向下调整算法，将父亲与孩子循环比较大小进行交换，形成新的堆，再次把堆顶元素与最后一个元素交换，使用向下调整成新的堆，反复进行即可删除堆

堆的排序   升序  降序

向上调整建堆，堆顶元素与最后一个元素交换，再次向上或向下调整，得到升序或降序

向上调整建堆

向下调整建堆

向上向下调整对比

向下调整时间复杂度分析

向上调整时间复杂度分析

总结

堆排序时间复杂度

堆的代码实现

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void Adjustdown(HPDataType* a, int parent);
void swap(Heap* hp, int child, int parent);

//函数实现
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
void swap( int *p1, int *p2)
{
	
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->a = NULL;
	free(hp);
	hp = NULL;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}

	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)//1未开劈空间 2.已满没有空间
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		Heap* tmp = (Heap*)realloc(hp->a, sizeof(HPDataType)* newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return NULL;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	//空间够  
	hp->a[hp->size] = x;
	hp->size++;
	//放进之后 向上调整形成新的堆
	Adjustup(hp->a, hp->size - 1);
}
//向xia调整
void Adjustdown(HPDataType* a,int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{     //右孩子小于huo大于左孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child= parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	//把第一个元素与最后一个交换，向下调整
	swap( &hp->a[0],&hp->a[hp->size-1]);
	hp->size--;
	Adjustdown(hp->a, hp->size, 0);

}
//取堆顶数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	
	return hp->size;
}

#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
void test()
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 60,50,6,8,14,7,3 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}HeapDestroy(&hp);
}
void HeapSort(int* a, int n)
{
	// 升序 -- 建大堆
	// 降序 -- 建小堆
	Heap hp;
	HeapInit(&hp);

	 //建堆--向上调整建堆
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

	// 建堆--向下调整建堆 --O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		// 再调整，选出次小的数
		AdjustDown(a, end, 0);

		--end;
	}
}
int main()
{
	test();
	
	return 0;
}