【数据结构】堆的复杂度，堆排序和TOP-K问题_topk堆排序平均时间复杂度

一、堆的时间复杂度

        堆通常是一个可以被看作一个完全二叉树，满二叉树也可以看做一个完全二叉树，所以我们可以用满二叉树来证明。

调整次数用N来表示，从倒数第二层开始调整（叶子节点不用调整）

1.向上调整建堆

        时间复杂度为  N * logN

        

2.向下调整建堆

        时间复杂度为 N

所以我们可知，向下调整建堆效率更高。

二、堆排序

        创建堆之后，我们选择以升序建大堆，降序建小堆。因为升序建小堆选出一次小数都，彼此的关系会改变，代价很大，降序同理。

void Swap(HPDataType* p1,HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(HPDataType* 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)
{
	//向下调整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
 
int main()
{
	int a[] = {7,8,3,5,1,9,4,5};
	HeapSort(a, sizeof(a) / sizeof(a[0]));
 
	return 0;
}

三、TOP-K问题

        TOP-K问题：求数据中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

这时我们就可以用堆排序来解决这个问题，先用数据中前K个数据来建堆。

求前K个最大数据，建小堆

求前K个最小数据，建大堆

然后用后N-K个数据跟堆顶进行比较，满足条件则替换堆顶元素，数据则用随机数来创建

我们以文件的形式进行模拟

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustUp(HPDataType* a, int child);
void HPInsert(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
bool HPEmpty(HP* php);
HPDataType HPTop(HP* php);
void HPDestroy(HP* php);
int Heapsize(HP* php);

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
 
 
void test1()
{
	HP hp;
	HPInsert(&hp);
	int arr[] = { 10,20,5,15,9,11 };
	int i = 0;
 
	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HPPush(&hp, arr[i]);
	}
 
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		printf("%d ", top);
		HPPop(&hp);
	}
 
	HPDestroy(&hp);
}
 
//void HeapSort(int* a, int n)
//{
//	HP hp;
//	HPInsert(&hp);
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		HPPush(&hp, a[i]);
//	}
//	i = 0;
//	while (!HPEmpty(&hp))
//	{
//		int top = HPTop(&hp);
//		a[i++] = top;
//		HPPop(&hp);
//	}
//
//	HPDestroy(&hp);
//}
 
//void HeapSort(int* a, int n)
//{
//	//向上调整建堆
//	int i = 0;
//	for (i = 1; i < n; i++)
//	{
//		AdjustUp(a, i);
//	}
//	int end = n - 1;
//	while (end)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		end--;
//	}
//}
 
void HeapSort(int* a, int n)
{
	//向下调整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
 
void creatNData()
{
	int n = 100000000;
	srand((unsigned)time(NULL));
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fin");
		return;
	}
	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
 
void PrintTopK(int k)
{
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fout");
		return;
	}
 
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("kminheap");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
 
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
 
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}
 
	int end = k - 1;
	while (end)
	{
		Swap(&kminheap[0], &kminheap[end]);
		AdjustDown(kminheap, end, 0);
		end--;
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}
 
int main()
{
	//test1();
	/*int a[] = {7,8,3,5,1,9,4,5};
	HeapSort(a, sizeof(a) / sizeof(a[0]));*/
	//creatNData();
	PrintTopK(5);
 
	return 0;
}

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
 
void HPInsert(HP* php)
{
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
 
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
 
void Swap(HPDataType* p1,HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustUp(HPDataType* a, int child)
{
	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 AdjustDown(HPDataType* 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 HPPush(HP* php, HPDataType x)
{
	assert(php);
 
	if (php->size == php->capacity)
	{
		int tmp = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* arr = (HPDataType*)realloc(php->a, tmp * sizeof(HPDataType));
		if (arr == NULL)
		{
			perror("HPPush");
			return;
		}
		
		php->a = arr;
		php->capacity = tmp;
	}
 
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a,php->size-1);
}
 
void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php->a));
 
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
 
	AdjustDown(php->a, php->size - 1, 0);
}
 
HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}
 
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
 
int Heapsize(HP* php)
{
	assert(php);
	return php->size;
}