树--堆和优先权队列

数据结构中的堆和栈与操作系统内存划分中的堆和栈没有关系

一、堆的定义

一个大小为n的堆是一棵包含n个结点的完全二叉树，其根节点称为堆顶。

根据堆中亲子结点的大小关系，分为大堆和小堆：
（1）最小堆：树中的每个结点的元素都小于或等于其孩子结点的元素。最小堆中堆顶存储的元素为整棵树中最小的

（2）最大堆：树中的每个结点的元素都大于或等于其孩子结点的元素。最大堆中堆顶存储的元素为整棵树中最大的

下列关键字序列为堆的是：（A）

A        100,60,70,50,32,65

B        60,70,65,50,32,100

C        65,100,70,32,50,60

D        70,65,100,32,50,60

E        32,50,100,70,65,60

F        50,100,70,65,60,32

二、堆的存储表示

所有的数组都可以表示成完全二叉树，但是不是所有的数组或完全二叉树都是堆

堆的逻辑结构：逻辑结构为完全二叉树

堆的物理结构：实际上的存储结构是数组

三、建堆算法的实现

最大堆向上调整思路：

向上调整代码实现：

//size为数组大小，child为新插入的数据位置
void AdjustUp(int *a,int size,int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//大堆
		//if (a[child] > a[parent])
		//小堆
		if(a[child]
		{
			//父子数值交换
			Swap(&a[child], &a[parent]);
 
			//更新父子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

最小堆向下调整思路：

即将其调整成最小堆，向下调整，将根结点与左右孩子中更小的那个交换

结束条件：①父亲<=小的孩子，则停止②调整至叶子结点

向下调整代码实现：

void AdjustDown(int *a,int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;//左孩子
	while (child
	{
		//选更大的孩子结点，child+1为右孩子
		//if (child+1a[child])
		//选更小的孩子节点
		if(child+11]
		{
			child++;//如果右孩子值更大/小，那么child指向右孩子
		}
		//大堆：如果大的孩子大于父亲则交换
		//if (a[child]>a[parent])
		//小堆，如果小的孩子小于父亲则交换
		if(a[child]
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

建堆算法实现思路：

这里建堆采用向上调整，删除采用向下调整。

删除操作采取数据交换的原因，是为了避免直接删除堆顶数据，导致整个数后面顺序全部改变。

接口函数中的Push与Pop操作的时间复杂度为O(logN)

建堆操作时间复杂度为O(N)：因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。

建堆算法代码实现：

头文件：

#pragma
#include
#include
#include
#include
#include
#include
 
typedef int HPDataType;
typedef struct heap
{
	int* a;
	int size;
	int capacity;
}HP;
 
void HeapCreate(HP* hp, HPDataType* a, int n);//构建一个堆
void HeapPrintf(HP* hp);//循环输出打印堆中元素
void Swap(HPDataType* px,HPDataType *py);
void AdjustUp(int* a, int size, int child);//向上调整
void AdjustDown(int* a,int size,int parent);//向下调整
void HeapInit(HP* hp);//堆的初始化
void HeapDestory(HP* hp);//堆销毁
void HeapPush(HP* hp,HPDataType x);//堆中插入数据
void HeapPop(HP* hp);//删除堆顶数据
HPDataType HeapTop(HP* hp);//获取堆顶数据
int HeapSize(HP* hp);//堆节点数量
bool HeapEmpty(HP* hp);//判空
void HeapSort(int* a, int n);//堆排序

源文件： 

#include"heap.h"
 
void HeapCreate(HP* hp,HPDataType *a,int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(hp->a, a, sizeof(HPDataType) * n);
	//void *memcpy(void *str1, const void *str2, size_t n) 
	//从存储区 str2 复制 n 个字节到存储区 str1。
	hp->size = hp->capacity = n;
	HeapSort(a, n);
}
void Swap(HPDataType* px,HPDataType* py)
{
	HPDataType* tmp = *px;
	*px = *py;
	*py = tmp;
}
 
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
 
 
void HeapDestory(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
 
//向上调整
//size为数组大小，child为新插入的数据位置
void AdjustUp(int *a,int size,int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//大堆
		//if (a[child] > a[parent])
		//小堆
		if(a[child]
		{
			//父子数值交换
			Swap(&a[child], &a[parent]);
 
			//更新父子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
//堆插入数据堆其他结点没有影响
//可能会影响它到根节点的路径上的结点关系
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size==hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp==NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size, hp->size - 1);
}
 
 
void AdjustDown(int *a,int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;//左孩子
	while (child
	{
		//选更大的孩子结点，child+1为右孩子
		//if (child+1a[child])
		//选更小的孩子节点
		if(child+11]
		{
			child++;//如果右孩子值更大/小，那么child指向右孩子
		}
		//大堆：如果大的孩子大于父亲则交换
		//if (a[child]>a[parent])
		//小堆，如果小的孩子小于父亲则交换
		if(a[child]
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
 
//再进行向下调整算法
void HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);//将堆顶数据与数组中最后一个数据交换
	hp->size--;//删除数组中的最后一个数据
	AdjustDown(hp->a, hp->size,0);//传入数组，数组的大小，向下调整起始位置
}
 
void HeapPrintf(HP* hp)
{
	for(int i=0;isize;i++)
	{
		printf("%d ",hp->a[i]);
	}
	printf("\n");
}
 
HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}
 
int HeapSize(HP* hp)
{
	return hp->size;
}
 
bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

 四、堆排序

 也就是将堆中的数据进行排序，原本堆是一个完全二叉树。堆排序的目的是将结点中的数字，按照从小到大，或者从大到小的方式存储在数组中。

也就是说如果有一个大堆，那么堆顶数据原本储在数组a[0]位置处。数组a中的数字存储顺序是无序的。堆排序的意义就是将数组中的按照一定的顺序排列。

 

堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

堆排序代码实现：

//向上调整
//size为数组大小，child为新插入的数据位置
void AdjustUp(int *a,int size,int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//大堆
		//if (a[child] > a[parent])
		//小堆
		if(a[child]
		{
			//父子数值交换
			Swap(&a[child], &a[parent]);
 
			//更新父子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
 
void AdjustDown(int *a,int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;//左孩子
	while (child
	{
		//选更大的孩子结点，child+1为右孩子
		//if (child+1a[child])
		//选更小的孩子节点
		if(child+11]
		{
			child++;//如果右孩子值更大/小，那么child指向右孩子
		}
		//大堆：如果大的孩子大于父亲则交换
		//if (a[child]>a[parent])
		//小堆，如果小的孩子小于父亲则交换
		if(a[child]
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int*a ,int n)
{
	//把a构建成堆
	for (int i = 0;i
	{
		AdjustUp(a, n, i);
	}
//降序排序
//	for (int i=(n-1-1)/2;i>=0;i--)
//	{
//		AdjustDown(a, n, i);
//	}
}