投稿
  1. 首页
  2. C

迅速掌握堆和堆排序的要点

code • 2022-4-9 • C • 阅读 76

迅速掌握堆和堆排序的要点,第1张

堆与栈，队列不一样。


堆的数据在物理上是一个数组，但在逻辑上是附加了条件的完全二叉树，父节点都小于子节点叫小堆反之叫大堆。


堆的插入与删除要求不改变原来的性质(大堆还是大堆，小堆还是小堆）。


先给出定义：

#include 
#include 
#include 


typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

//初始化
void HPInit(HP*php);
//销毁
void HPDeatory(HP* php);
//插入
void HPPush(HP* php,HPDataType x);
//删除
void HPPop(HP* php);
//打印
void HPPrint(HP* php, int size);



void HeapSort1(HPDataType* a, int size);
void HeapSort2(HPDataType* a, int size);

这里插入与删除都是以小堆为例 。


堆的插入：先在数组最后一个元素的后面插入，为了保证它原来的大(小)堆有向上进行调整算法。


向上调整：

找到最后一个元素的父节点，如果父节点大于它就交换两个值，再进行迭代(child = parent;parent = (child-1)/2)。


什么时候结束？parent<=0还是child<=0?因为他的所有祖先都要比较所以应该是child==0结束。


因此向上调整不一定要到顶部，也可能中间就停止了。


所以可以写出代码：

//向上调整(向上建堆)
void AdjustUp(HPDataType* a, int i)
{
	assert(a);
	int child = i, parent = (i - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			//交换
			Sweap(&a[child], &a[parent]);
			child = parent, parent = (child - 1) / 2;
		}
		else//不交换了，就退出循环
		{
			break;
		}
	}
}
//插入
void HPPush(HP* php,HPDataType x)
{
	assert(php);
	//扩容？
	if (php->size == php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HP* tmp = (HP*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		assert(tmp);
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入
	php->a[php->size] = x;
	php->size++;
	//调整，从最后一个数据向上调整
	AdjustUp(php->a,php->size-1 );//传入数组与最后一个元素的下标
}

堆的删除：要求删除根节点也就是删除最大或者最小的数据，而且不改变堆的性质

第一步：交换头和尾的数据，第二步：控制数组的size向前挪(size--)就可以把数据删掉，和顺序表的删除是一样的，第三步：把交换后的堆顶的元素向下调整。


向下调整：

从下标为0的位置开始和自己的两个孩子中最小的比较(因为要排的是小堆),如果两个孩子里最小的小于它就交换。


然后进行迭代(parent = child;child = parent*2+1)。


什么时候结束？child不在数组范围内了就可以结束了，即：child>=size的时候结束。


要注意右孩子是否存在 。


//向下调整（从start开始往下建堆）   
void AdjustDown(HPDataType* a, int size, int start)
{
	assert(a);
	int parent = start, child = (parent) * 2 + 1;
	while (child < size)
	{
		//找到孩子中最小的
		if (child + 1 < size && a[child] > a[child + 1])//child+1a[0], &php->a[php->size - 1]);
	//删除
	php->size--;
	//从头向下建堆
	AdjustDown(php->a, php->size, 0);
}

从堆数据的插入和删除可以看出，堆存储数据的优势是效率高。


假设有n个数据，插入：每次向上进行调整算法要logn次；删除：每次向下调整算法也要logn次。


O(logn)。


建立堆有两个方法

1.从第二个数据开始每个数据当作新插入的数据进行向上调整

2.从最后一个父节点的子树向下调整，往前遍历完所有的的树

是大堆还是小堆取决于具体的代码

堆排序的实现有两步：1.建大堆或小堆；2.交换第一个和最后一个再从上往下建堆

对于一个给定的数组来说要在空间复杂度为O (1)的前提下完成建堆有两个思路：

第一个：从第二个数据开始每个数据当作新插入的数据进行向上调整

//向上调整(向上建大堆)
void AdjustUp(HPDataType* a, int i)
{
	assert(a);
	int child = i, parent = (i - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			//交换
			Sweap(&a[child], &a[parent]);
			child = parent, parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//从第二个数开始每个都看成插入进来，再进行调整
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}

第二个：从最后一个父节点的子树向下调，往前遍历完所有的的树

//向下调整（从下标i开始往下建堆）   
void AdjustDown(HPDataType* a, int size, int start)
{
	assert(a);
	int parent = start, child = (parent) * 2 + 1;
	while (child < size)
	{
		//找到孩子中最大的
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Sweap(&a[parent], &a[child]);
			parent = child, child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i>0,因为第一个也要进行比较
	{		
		//从下标i开始往下建堆     大堆
		AdjustDown(a, size, i);
	}

这里相对难以理解的是：

要排升序建大堆，派降序要建小堆。


假设要升序排列

这是一串随机的数据：

 下面是第一步：用其中一种方法建个大堆

 第二步：

从图中可以看出最大的一个数32564已经到了他应该去的位置——最后一个。


然后我们再把剩下的数据也就是size-1个数据重复第一步就可以在堆顶找到次大的数据。


然后重复就可以在空间复杂度为O(1)的条件下完成升序排列。


 

for (int i = size - 1; i > 0; i--)
	{
		Sweap(&a[0], &a[i]);
		AdjustDown(a, i, 0);//i-1为什么不行？
		//这里的逻辑是交换后从a[0]到a[i-1]个数的调整，所以传i就是调整到下标为i-1的位置。

如果写成i-1就会导致前面两个没有排列。


	}

堆排序有两种建大堆或小堆的方法，这两种方法时间复杂度不同

第一种，每次都当新插入的元素：AdjustUp()--O(NlogN),

第二种：从最后一个父节点的子树：AdjustDown--O(N);

所以AdjustDown要快一点，证明用到了错位相减。


放在最后，有兴趣可以查看。


下面的是全部的代码：

#include 
#include 
#include 


typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

//初始化
void HPInit(HP*php);
//销毁
void HPDeatory(HP* php);
//插入
void HPPush(HP* php,HPDataType x);
//删除
void HPPop(HP* php);
//打印
void HPPrint(HP* php, int size);

void HeapSort1(HPDataType* a, int size);
void HeapSort2(HPDataType* a, int size);
#include "HP.h"

//初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//销毁
void HPDeatory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = 0;
	php->size = 0;
	php->capacity = 0;
}
//交换
void Sweap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
//向上建堆
void AdjustUp(HPDataType* a, int i)
{
	assert(a);
	int child = i, parent = (i - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			//交换
			Sweap(&a[child], &a[parent]);
			child = parent, parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}
//从下标i开始往下建堆     大堆
void AdjustDown(HPDataType* a, int size, int start)
{
	assert(a);
	int parent = start, child = (parent) * 2 + 1;
	while (child < size)
	{
		//找到孩子中最大的
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Sweap(&a[parent], &a[child]);
			parent = child, child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//插入
void HPPush(HP* php,HPDataType x)
{
	assert(php);
	//扩容？
	if (php->size == php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HP* tmp = (HP*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		assert(tmp);
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入
	php->a[php->size] = x;
	php->size++;
	//调整
	AdjustUp(php->a,php->size-1 );
}
//删除
void HPPop(HP* php)
{
	assert(php);
	//交换
	Sweap(&php->a[0], &php->a[php->size - 1]);
	//删除
	php->size--;
	//从头向下建堆
	AdjustDown(php->a, php->size, 0);
}








//打印
void HPPrint(HP* php, int size)
{
	assert(php);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}


void my_HeapSort1(HPDataType* a, int size)
{
	//从第二个数开始每个都看成插入进来，在进行调整
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}
	
	//把第一个和最后一个交换再次建堆
	for (int i = size-1; i > 0; i--)
	{
		Sweap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

void my_HeapSort2(HPDataType* a, int size)
{
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i>=0,因为第一个也要进行比较
	{
        //从下标i开始往下建堆     大堆
		AdjustDown(a, size, i);
		
	}
	for (int i = size - 1; i > 0; i--)
	{
		Sweap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
        //i-1为什么不行？前面两个没有排列，如果用另一种方法建堆，可能结果没错，但是这本身是不对的。


	}
}
#include "HP.h"
void test1()
{
	int a[] = { 763 ,1,23,63,542,5643,97,41,33,4613,32564,313,313,631,6 };
	int len = sizeof(a) / sizeof(a[0]);
	my_HeapSort1(a, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void test2()
{
	int a[] = { 763 ,1,23,63,542,5643,97,41,33,4613,32564,313,313,631,6 };
	int len = sizeof(a) / sizeof(a[0]);
	my_HeapSort2(a, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	//复习堆的基本操作
	//HP hp;
	//HPInit(&hp);
	//HPPush(&hp, 5);
	//HPPush(&hp, 4);
	//HPPush(&hp, 8);
	//HPPush(&hp, 150);
	//HPPush(&hp, 95);
	//HPPrint(&hp, hp.size);
	//HPPop(&hp);
	//HPPrint(&hp, hp.size);
	//HPPop(&hp);
	//HPPrint(&hp, hp.size);
	//HPPop(&hp);
	//HPPrint(&hp, hp.size);
	//HPPop(&hp);
	//HPPrint(&hp, hp.size);


	test1();
	test2();

	return 0;
}

TopK问题：

TopK也就是一堆数据中求取最大或者最小的k个数，这种题一般方法：

排序：qsort,冒泡，堆等等 。


但是，如果数据非常庞大呢？比如70亿(n)个数据中取最大的k个，这样内存就会不够。


这个时候堆就闪亮登场了：

先取前k个数据建一个小堆，然后遍历后面的n-k个，如果比堆顶的数据大就把它的值赋给堆顶，再向下调整成一个新的堆。


void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	int* kminHeap = (int*)malloc(sizeof(int)*k);
	assert(kminHeap);

	for (int i = 0; i < k; ++i)
	{
		kminHeap[i] = a[i];
	}

	// 建小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(kminHeap, k, j);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);
		}
	}

	for (int j = 0; j < k; ++j)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2305] = 1000000 + 6;
	a[99] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[0] = 1000000 + 1000;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();

	return 0;
}

 

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/568270.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表（0条）

保存