手撕堆的实现（堆排序，Topk问题）——单手吊打数据结构

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child- 1)/2;
	while (child > 0)//不能用parent>=0判断，因为parent始终不小于0
	{
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	
}

到这里了咱光说不练假把式是吧，看看堆插入怎么搞：

void HeapPush(Heap* hp, HPDataType x)
{
	int i;
	assert(hp);
	if (hp->size == hp->capacity)
	{
		hp->capacity *= 2;
		hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);//插入数据

	}
	else
	{
		hp->a[hp->size] = x;
		hp->size++;
		AdjustUp(hp->a,hp->size-1);//调整堆数据
	}
}

那么出堆也是同理：

void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(hp->a[hp->size-1], hp->a[0]);
	hp->size--;
	AdjustDown(hp->a, hp->size,0);
}

送上全部代码：
==Heap.h==

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

==Heap.c==

# define _CRT_SECURE_NO_WARNINGS 
#include"heap.h"
void Swap(HPDataType* x1, HPDataType* x2)
{
	int tem;
	tem = x1;
	x1 = x2;
	x2 = tem;
}

void AdjustDown(HPDataType* a, int n, int root)
{
	assert(a);
	int parent = root;
	int child = (parent/2)-1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

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

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp&& a);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	hp->size = n;
	hp->capacity = n;
	return hp;
	for (int i = 0; i < n; i++)
	{
		hp->a[i] = a[i];
	}
	for (int i = (n - 2) / 2; i >=0 ; i-- )
	{
		AdjustDown(hp->a,hp->size,i);
	}
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	int i;
	assert(hp);
	if (hp->size == hp->capacity)
	{
		hp->capacity *= 2;
		hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);

	}
	else
	{
		hp->a[hp->size] = x;
		hp->size++;
		AdjustUp(hp->a,hp->size,hp->size-1);
	}
}
	
void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(hp->a[hp->size-1], hp->a[0]);
	hp->size--;
	AdjustDown(hp->a, hp->size,0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

int HeapEmpty(Heap* hp)
{
	return hp->size == 0;
}

void HeapPrint(Heap* hp)
{
	assert(hp);
	int i;
	for (i = 0; i < hp->size; i++)
	{
		printf("%s ", hp->a[i]);
	}
}

调整算法的时间复杂度对比🤔

其实堆的插入与堆的删除时间复杂度都是一样的：logN，其实就是向上调整算法和向下调整算法的时间复杂度，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数），类比为二分搜索就很好理解，因此他和 ==qsort== 是一个量级的。

void Heapsort(int* a, int n)
{
	assert(a);
	//for(int i =1;i<n;i++)
	//{
	//AdjustUp(a, n, i);//使用向上调整建堆
	//}
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//使用向下调整建堆倒着调整
	int tail = n - 1;
	while(tail>0)
	{
		Swap(&a[0], &a[tail]);//前后交换
		AdjustDown(a, n, 0);//重新调整堆的结构
		tail--;
	}
}

//1. 找最大的K个元素
//假设堆为小堆
void SmallTopK(int* a, int n, int k)
{
	Heap hp;
	HeapCreate(&hp, a, n);
	int i;
	for (i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}	//筛查，不符合条件的替换掉
	}
	for (i = 0; i <k; i++)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
}

//2. 找最小的K个元素
//假设堆为大堆
void BigTopK(int* a, int n, int k)
{
	Heap hp;
	HeapCreate(&hp, a, n);
	int i;
	for (i = k; i < n; i++)
	{
		if (a[i] < HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
		for (i = 0; i < k; i++)
		{
			printf("%d ", HeapTop(&hp));
			HeapPop(&hp);
		}
	}
}