二叉树大小堆算法改进通解

 堆的向下调整算法

建堆需要用到向下调整

        建堆的时候将数据存储到完全二叉树中，但是完全二叉树是无序的不一定具有堆的特性，需要进行child 和parent的比较，将根节点往下调，直到满足堆特性

 对于上面的右图，100的左右 子树都已满足小堆的特性，只需要将100往下调整即可

对于上面的左图，因为以6 和9为根节点的子树并不满足小堆的特性，所以需要先将6和9这两棵树调整成小堆，对于6，就相当于要先将1和5两棵子树调整成小堆，再让根节点6向下调整，最终当6和9都满足小堆的特性后，再来调3.

删除需要用到向下调整   

        删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

上图可以看出 ，交换之前是个大堆 ，93和45交换后，删除93，此时80和48这两棵子树，已经满足大堆性质，所以需要将45往下调整使整体满足大堆序。

由于之前的代码无法直接适用于数组建堆后，通过向下调整法形成大小堆，堆的大小需要通过修改代码的判断符号 > 或者 < 来进行修改 ，这种每次都要修改源代码，并不提倡。

 如果想让代码大小堆都可以创建-----上述向下调整方式就必须写两份------实现创建大小堆没有任何问题，但是不好------->原因：代码复用性不好

代码的逻辑是相同的，唯一的不同：只是：只是元素的比较方式不同

优化：将比较的方法不要写死，将其抽离出来，让用户可以进行配置

通过引用函数指针的方法，让指针变量指向一个写好的比较函数，最后使用时仅需要进行传参即可

  int (*Cmp) (HDataType , HDataType );   创建一个函数指针变量Cmp

  函数指针变量 ： 可以指向任何有两个HDataType参数以及一个int类型返回值的所有函数

  Cmp是函数指针变量：Cmp既可以指向Less ，也可以指向Greater
  Cmp的类型： int (*) (HdataType , HdataType )  

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

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

头文件 Heap.h

#pragma once

//假设数据为整型
typedef int HDataType; 

// CMP就是 int (*) (HdataType , HdataType )类型的别名  
typedef int(*CMP)(HDataType , HDataType); 

int Less(HDataType left, HDataType right);
int Greater(HDataType left, HDataType right);


typedef struct Heap
{
	HDataType* array;
	int capacity;
	int size;
	// int (*Cmp) (HDataType, HDataType);  函数指针变量Cmp,但是这种方法不直观，用取别名代替
	CMP Cmp;
}Heap;


// 堆的初始化
void HeapInit(Heap* hp, int initCap,CMP cmp);
// 堆的构建
void HeapCreate(Heap* hp, HDataType* a, int n , CMP cmp);
// 堆的插入
void HeapPush(Heap* hp, HDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HDataType HeapTop(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 对数组进行堆排序
void HeapSort(int* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 测试
void TestHeap();

源文件 Heap.cpp

#include
#include "Heap.h"
#include
#include
#include
using namespace std;

int Less(HDataType left, HDataType right)
{
	return left < right;
}
int Greater(HDataType left, HDataType right)
{
	return left > right;
}


// 初始化一个空堆，initCap为初始的容量
void HeapInit(Heap* hp , int initCap ,CMP cmp) 
{
	assert(hp); // 先判断堆存不存在
	initCap = initCap < 10 ? 10 : initCap;
	hp->array = (HDataType*)malloc(sizeof(HDataType) * initCap); // 保证最少开辟10个空间
	if (NULL == hp->array)//判断空间是否开辟成功
	{
		// 开辟失败
		assert(0);
		return;
	}

	hp->capacity = initCap;
	hp->size = 0;
	hp->Cmp = cmp;
}

void Swap(HDataType* left, HDataType*right)
{
	HDataType tmp = *left;
	*left = *right;
	*right = tmp;
}

void AdjustDown(Heap*hp , int parent)
{
	// 默认左子节点child为parent的较小的孩子
	int size = hp->size;
	int* array = hp->array;
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找较小的孩子，如果右子节点大于左子节点，将child标为右节点的下标
		if (child + 1 < size && hp->Cmp(array[child+1] , array[child]) )
			child += 1; 

		// 已找到较小的孩子，检测parent是否满足堆的性质
		if (hp->Cmp( array[child] , array[parent]) )
		{
			Swap(&array[child] , &array[parent]);
			parent = child; //调节后可能子树又不满足堆的性质，所以继续往下调
			child = parent * 2 + 1;
		}
		else
			return;
	}
}


// 用数组中的元素创建堆
void HeapCreate(Heap* hp, HDataType* pArray, int size, CMP cmp)
{
	// 1.先将数组中的元素放在堆结构中
	HeapInit(hp, size , cmp);
	memcpy(hp->array, pArray, sizeof(HDataType) * size);  //void* memcpy( 目标内存, 源内存, 字节个数);
	hp->size = size;

	// 2.进行向下（上）调整  找到第一个非叶子节点进行调整（最后一个节点size-1的双亲节点）
	//  下标 ((size-1) - 1)/2 = (size-2)/2
	for (int root = (size - 2) / 2; root >= 0; root--)
		AdjustDown(hp , root);
}

void CheckCapacity(Heap* hp)
{
	assert(hp);
	// 检测是否需要扩容
	if (hp->capacity == hp->size)
	{
		// 1.开辟新空间
		int NewCapacity = hp->capacity * 2;
		HDataType* tmp = (HDataType*)malloc(sizeof(HDataType) * NewCapacity);
		if (NULL == tmp)
		{
			assert(0);
			return;
		}

		// 2. 拷贝原空间元素
		

		// 法二 ：
		for (int i = 0; i < hp->size; i++)
			tmp[i] = hp->array[i];

		// 3. 释放旧空间
		free(hp->array);

		// 4. 使用新空间
		hp->array = tmp;
		hp->capacity = NewCapacity;
	}
}
		
void AdjustUP(Heap*hp , int child)
{
	int parent = ((child - 1) >> 1); // 右移一位相当于除二
	HDataType* array = hp->array;
	while (child)// 最差情况一直移到0号节点位置才调整好
	{
		
		if (hp->Cmp(array[child] , array[parent]) )
		{
			Swap(&array[child], &array[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			return; //插入时刚好满足整体小堆
	}
}

// 堆的插入
void HeapPush(Heap* hp, HDataType data)
{
	// 0. 检查是否需要扩容
	CheckCapacity(hp);
	// 1. 将新元素插入到数组的末尾，即：将新元素插入到完全二叉树的最后
	hp->array[hp->size++] = data;

	// 2.新元素插入后，可能会破坏堆的性质，采用向上调整（数据内存，空间大小，需要调整的元素位置）
	AdjustUP(hp, hp->size - 1);
}

// 堆顶的删除
void HeapPop(Heap* hp)
{
	if (HeapEmpty(hp))
		return;

	//交换堆顶和最后一个元素的位置
	Swap(&hp->array[0], &hp->array[hp->size - 1]);
	// 删除最后一个元素
	hp->size--;
	AdjustDown(hp , 0);// 从上往调 parent坐标为0
}

// 获取堆顶的数据
HDataType HeapTop(Heap* hp)
{
	assert( !HeapEmpty(hp) ); // 先堆是否为空
	return  hp->array[0]; //堆顶编号为0
}

// 堆为空返回非0值
int HeapEmpty(Heap* hp)
{
	assert(hp); // 进行指针判空
	return 0 == hp->size;
}


// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp); // 进行指针判空
	return  hp->size;
}

// 对数组进行堆排序
void HeapSort(int* a, int n);

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->array);
	hp ->array = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

void TestHeap()
{
	int array[] = { 3, 6, 9, 1, 5, 2, 0, 7, 8, 4 };
	Heap hp;
	HeapCreate(&hp, array, sizeof(array) / sizeof(array[0]), Greater);
	cout << "heap size "<< HeapSize(&hp)<< endl;       // 输出堆的元素大小
	cout << "heap top =" <array :" << hp.array << endl;         // 输出堆数据域空间的首地址

	int i = 0;
	while ( i < hp.size)
	{
		cout  << hp.array[i++] <<" "; // 打印调整好的堆元素
	}

	cout << endl;
	
	HeapPop(&hp); // 去除堆顶元素
	for(int j =0 ; j 
 
Creat_Heap.cpp
 
#include"Heap.h"
int main()
{
	TestHeap();
	return 0;
}
 
 
HeapCreate( &hp , array , sizeof(array) / sizeof(array[0]) , Greater); 创建大堆
 
 
 HeapCreate(&hp, array, sizeof(array) / sizeof(array[0]), Less);创建小堆