数据结构----堆 和 堆排序 代码

#pragma once

											/*堆*/
//完全二叉树
//可以用数组存，所以实现和数据结构很类似

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>/**/
#include <stdbool.h>

#define InitSize 100
//#define AddSize 50
//可以直接扩大两倍，不一定固定扩大的个数

typedef int HeapElemtype;

typedef struct Heap
{
	HeapElemtype* a;
	int size;
	int capacity;
}Hp;

void HeapInit(Hp* heap);
void HeapDestroy(Hp* heap);

void HeapPush(Hp* heap, HeapElemtype x);
void AdjustUp(HeapElemtype* a,int child);

void HeapPop(Hp* heap);
void AdjustDown(HeapElemtype* a, int n, int parent);

void Swap(HeapElemtype* a, HeapElemtype* b);

bool HeapEmpty(Hp* heap);

HeapElemtype HeapTop(Hp* heap);
int HeapSize(Hp* heap);

//堆排序
void HeapSort(HeapElemtype* a, int n);

#include "Heap.h"

void HeapInit(Hp* heap)
{
	assert(heap);

	Hp* temp = (HeapElemtype*)malloc(sizeof(Hp) * InitSize);
	if (temp == NULL)
	{
		perror("malloc fail");
		return;
	}

	heap->a = temp;
	heap->capacity = InitSize;
	heap->size = 0;
}

void HeapDestroy(Hp* heap)
{
	assert(heap);

	heap->capacity = 0;
	heap->size = 0;
	free(heap->a);
	heap->a = NULL;
}

void HeapPush(Hp* heap, HeapElemtype x)
{
	Hp* temp;
	if (heap->size == heap->capacity)
	{//要扩容
		temp = (Hp*)realloc(heap->a,sizeof(Hp) * (heap->capacity * 2));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}		
	
		heap->a = temp;
		heap->capacity *= 2;
	}

	//插入
	heap->a[heap->size] = x;
	heap->size++;

	//向上调整！！！！！！！！
	/*插入：向上调整*/
	AdjustUp(heap->a, heap->size - 1);
}

//小根堆:只要插入的数据比父亲小，就升辈分
//大                         大

//传参为数组的向上调整代码
void AdjustUp(HeapElemtype* a, int child)
{
	HeapElemtype temp = a[child];
	int parent = (child - 1) / 2;

	//循环上移，直到合适位置
	//也可以写成：while (child >= 0)，注意：不是while (parent >= 0),因为最坏的情况是孩子走到根节点，而不是父亲走到根节点
	//但该种写法的while 内部要写为：if (heap->a[child] < heap->a[parent])交换；else break;
	while (a[child] < a[parent])
	{
		//调整数组元素
		Swap(&a[child], &a[parent]);

		//更新下标，方便后续继续调整
		child = parent;
		parent = (child - 1) / 2;
	}
}

void Swap(HeapElemtype* a, HeapElemtype* b)
{
	HeapElemtype temp = *a;
	*a = *b;
	*b = temp;
}

//注意堆中删除数一般为删除堆顶数据，因为删除堆的最后一个没有意义
//删除数据：先交换首尾数据，再将根和最小的孩子比较，如果根 < 最小的孩子----->不动；否则，向下调整/*删除：向下调整*/
void HeapPop(Hp* heap)
{
	assert(heap);
	assert(heap->size);

	//交换首尾数据
	Swap(&heap->a[0], &heap->a[heap->size - 1]);

	heap->size--;

	//向下调整
	AdjustDown(heap->a, heap->size, 0);/*注意，并不是所有情况都是删堆顶,所以要传入一个parent参数*/
}

//返回堆顶
HeapElemtype HeapTop(Hp* heap)
{
	assert(heap);
	assert(heap->size);

	return heap->a[0];
}

//传参为数组的向下调整代码
void AdjustDown(HeapElemtype* a, int n, int parent)
{
	int childl = parent * 2 + 1, childr = parent * 2 + 2;
	int child = a[childl] < a[childr] ? childl : childr;

	//也可写成：child + 1 < heap->size && a[child + 1] < a[child]  child++;
	while (child < n/*不仅要注意这个条件，同时要注意要写在前面*/ && a[parent] > a[child])
	{
		Swap(&a[parent], &a[child]);

		parent = child;
		childl = parent * 2 + 1, childr = parent * 2 + 2;
		child = a[childl] < a[childr] ? childl : childr;
	}
}

bool HeapEmpty(Hp* heap)
{
	assert(heap);

	return heap->size == 0;
}

int HeapSize(Hp* heap)
{
	assert(heap);

	return heap->size;
}

//堆排序：不要建堆，只是要用到里面的向上调整，所以传参不要传堆，而是传数组------节省建堆的空间和拷贝数据的消耗
// 堆只是一个数据结构，而不是一个排序方法，排序只是单独的把其向上调整的地方分离出来，使得只用调整数组，不去建堆
// 这也是为什么向上调整AdjustUp和向下调整AdjustDown部分传参不是传堆的地址，而是传数组地址的原因
//void HeapSort(Hp* heap)
//小堆：排降序	大堆：排升序------升降序看的是最后数组的顺序
void HeapSort(HeapElemtype* a, int n)
{
	//建堆--向上调整建堆
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//向下调整建堆
	//因为一个向上调整，一个向下调整很麻烦，所以把向上调整的部分可换为向下调整
	//要确保每个孩子是堆，所以从下往上调整，又因为叶子节点就是堆，所以要找最后一个非叶子节点
	//也就是从最后一个叶子的父节点开始调整
	for (int i = ((n - 1/*最后一个叶子的下标*/) - 1) / 2/*最后一个孩子的父亲*/; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//输出：输出队首，然后向下调整------先交换首尾，再size--，再向下调整
	int size = n;
	while (size)
	{
		Swap(&a[0], &a[size - 1]);
		size--;
		AdjustDown(a, size, 0);
	}
}

										/*堆*/

#include "Heap.h"

void HeapPrint(Hp* heap)
{
	//按照直接通过数组打印------满足堆的形态，但不是有序的，因为不是输出堆顶元素（堆顶元素一定是该堆的最值）
	//for (int i = 0; i < heap->size; i++)
	//{
	//	printf("%d ", heap->a[i]);
	//}
	//printf("\n");

	//按照Pop打印
	//while (!HeapEmpty(&heap))不能传地址,已经是指针了
	while (!HeapEmpty(heap))
	{
		//不能传地址，已经是地址
		printf("%d ", HeapTop(heap));
		//不能传地址，已经是地址
		HeapPop(heap);
	}
	printf("\n");
}

void test01()
{
	Hp heap;
	HeapInit(&heap);
	HeapElemtype a[] = { 10, 15, 56, 25, 30, 70, 0 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&heap, a[i]);
	}
	HeapPrint(&heap);
}

void test02()
{
	Hp heap;
	HeapInit(&heap);
	//HeapElemtype a[] = { 10, 15, 56, 25, 30, 70, 0 };
	HeapElemtype a[] = { 15, 21, 10, 2121, 1002,2 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&heap, a[i]);
	}
	HeapPrint(&heap);
	HeapPop(&heap);
	HeapPrint(&heap);

	printf("堆顶元素为：%d\n", HeapTop(&heap));
}

void test03()
{
	Hp heap;
	HeapInit(&heap);
	HeapElemtype a[] = { 15, 21, 10, 2121, 1002,2 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&heap, a[i]);
	}

	HeapPop(&heap);
	HeapPrint(&heap);
}

void test04()
{
	HeapElemtype a[] = { 15, 21, 10, 2121, 1002, 2 };
	HeapSort(&a, sizeof(a) / sizeof(a[0]));

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
		printf("%d ", a[i]);
	printf("\n");
}

int main()
{
	//test01();
	//test02();
	//test03();
	test04();

	return 0;
}