【数据结构】用堆实现排序

1.升序------建大堆

堆的时间复杂度N*logN

#include<stdio.h>

void Swap(int* p1, int* p2)
{
	int x = *p1;
	*p1 = *p2;
	*p2 = x;
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}

}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//筛选子节点中较大的数
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		//父子节点比较后进行交换
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


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

	//自己进行调整
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end,0);
		--end;
	}

}

int main()
{
	int a[10] = { 23,2,45,3,67,55,41,32,12,48 };
	HeapSort(&a, 10);
	for (int i = 0;i < 10;i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

2.降序------建小堆

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>

void Swap(int* p1, int* p2)
{
	int x = *p1;
	*p1 = *p2;
	*p2 = x;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//筛选子节点中较小的数
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		//父子节点比较后进行交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void PrintTopk(const char*file, int k)
{
	//1.建堆——用file中前k个元素建小堆
	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);

	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//读出前k个数据建小堆
	for (int i = 0;i < k;i++)
	{
		fscanf(fout, "%d", &topk[i]);
	}

	for (int i = (k -1-1) / 2;i >= 0;i--)//k-1是最后一个数据的下标，在-1除以2是找到它的父节点
	{
		AdjustDown(topk, k, i);
	}

	//将剩余n-k个元素依次与堆顶元素进行交换，不满则替换
	int val = 0;
	int ret = fscanf(fout, "%d", &val);
	while (ret != EOF)
	{
		if (val > topk[0])
		{
			topk[0] = val;
			AdjustDown(topk, k, 0);
		}

		ret = fscanf(fout, "%d", &val);
	}

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

	free(topk);
	fclose(fout);
}

void TestTopy()
{
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (size_t i = 0;i < n;i++)
	{
		int x = rand() % 10000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);

	PrintTopk(file, 10);
}


int main()
{
	TestTopy();
	return 0;
}