Heap.h
代码语言：javascript复制#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);Heap.c
代码语言：javascript复制#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);
}
}HeapTest.c
参考代码，具体的请自行更改使用
代码语言：javascript复制 /*堆*/
#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("堆顶元素为：%dn", 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;
}
