二、堆的实现

typedef int HPDataType;typedef struct Heap {HPDataType* a;int size;//有效数据个数int capacity;//数组大小
}HP;

主要接口：

//堆初始化
void HPInit(HP* php);
//堆的插入(插入后保持为堆)
void HPPush(HP* php, HPDataType x);
//向上调整
AdjustUp(HPDataType* a, int chlid);
//堆的删除(删除堆顶元素)
void HPPop(HP* php);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//取堆顶
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);
//堆的销毁
void HPDestroy(HP* php);//交换数据
void Swap(HPDataType* p1, HPDataType* p2);

2.1 堆初始化

void HPInit(HP* php) {assert(php);php->a = NULL;php->size = 0;php->capacity = 0;}

和之前顺序表的初始化一样，把数组置空，大小和容量都为空。

2.2 堆的销毁

void HPDestroy(HP* php) {assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}

释放我们开辟的数组空间，其他都置为空。

2.3 交换数据

void Swap(HPDataType* p1, HPDataType* p2) {HPDataType temp = 0;temp = *p1;*p1 = *p2;*p2 = temp;
}

定义一个交换函数，后面操作会用到。

2.4 插入数据(插入到堆尾)

void HPPush(HP* php, HPDataType x) {assert(php);//扩容if (php->size == php->capacity){int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* temp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity = Newcapacity;}php->a[php->size++] = x;//向上调整AdjustUp(php->a, php->size-1);
}

前面的插入操作和顺序表都插入一样，我们插入到堆的最后面，同时我们需要一个向上调整函数来保持结构仍为堆。

2.5 向上调整

AdjustUp(HPDataType* a, int chlid) {//父节点int parent = (chlid - 1) / 2;//先上调整while (chlid > 0){if (a[chlid] < a[parent]){Swap(&a[parent], &a[chlid]);//新的父子节点chlid = parent;parent = (parent - 1) / 2;}else{break;}}}

我们从子节点找它的父节点，比较父子节点的大小，如果堆为小堆，则谁更小谁在上面，反之如果为大堆，则谁更大谁在上面。

void HPPop(HP* php) {assert(php);assert(php->size > 0);//把堆顶元素和最后一个元素交换位置Swap(&php->a[0],&php->a[php->size - 1]);php->size--;//向下调整AdjustDown(php->a,php->size,0);
}

堆的删除操作，我们先把堆顶元素和堆尾元素交换位置，最后堆的长度减一即可(可以不用删除)，最后通过向下调整来保持堆的结构。

2.7 向下调整

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[parent], &a[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}

我们通过父节点来找到子节点，我们首先找到左右节点中最小的(反之如果是大堆找最大的)，找到后比较子节点和父节点中最小的交换位置(反之如果是大堆找最大的)。

//取堆顶
HPDataType HPTop(HP* php) {assert(php);return php->a[0];
}

因为堆是通过数组实现的，所以堆顶即为数组第一个元素。

2.9 判空

bool HPEmpty(HP* php) {assert(php);return php->size == 0;
}

测试代码：

#include"Heap.h"int main() {HP hp;HPInit(&hp);//初始化堆int a[] = { 50,100,70,65,60,32 };for(int i = 0; i < sizeof(a) / sizeof(a[0]);i++){//把数组的内容依次插入到堆中HPPush(&hp, a[i]);}while (!HPEmpty(&hp)){    printf("%d\n", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);
}

完整代码

//堆初始化
void HPInit(HP* php) {assert(php);php->a = NULL;php->size = 0;php->capacity = 0;}//交换数据
void Swap(HPDataType* p1, HPDataType* p2) {HPDataType temp = 0;temp = *p1;*p1 = *p2;*p2 = temp;
}//向上调整
AdjustUp(HPDataType* a, int chlid) {//父节点int parent = (chlid - 1) / 2;//先上调整while (chlid > 0){if (a[chlid] < a[parent]){Swap(&a[parent], &a[chlid]);//新的父子节点chlid = parent;parent = (parent - 1) / 2;}else{break;}}}//堆的插入(插入后保持为堆)
void HPPush(HP* php, HPDataType x) {assert(php);//扩容if (php->size == php->capacity){int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* temp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity = Newcapacity;}php->a[php->size++] = x;//向上调整AdjustUp(php->a, php->size-1);
}//向下调整
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[parent], &a[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}//堆的删除(删除堆顶元素)
void HPPop(HP* php) {assert(php);assert(php->size > 0);//把堆顶元素和最后一个元素交换位置Swap(&php->a[0],&php->a[php->size - 1]);php->size--;//向下调整AdjustDown(php->a,php->size,0);
}
//取堆顶
HPDataType HPTop(HP* php) {assert(php);return php->a[0];
}
//判空
bool HPEmpty(HP* php) {assert(php);return php->size == 0;
}
//堆的销毁
void HPDestroy(HP* php) {assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}

三、堆的创建

前面我们通过数组插入堆来建堆，我们还可以通过其他方法来创建堆

int main() {HP hp;int a[] = { 50,100,70,65,60,32 };HPInitArray(&hp,a,sizeof(a) / sizeof(a[0]));
}

1.向上调整建堆

void HPInitArray(HP* php, HPDataType* a, int n) {//为堆开辟空间php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");return;}//拷贝数组的值到堆中memcpy(php->a, a, sizeof(HPDataType) * n);php->size = php->capacity = n;//向上调整建堆  O(N*longN)for (int i = 1; i < php->size; i++){AdjustUp(php->a, i);}
}

我们从堆的第二个节点开始先上开始调整的。

向上调整建堆的时间复杂度为：O(N*longN)

2.向下调整建堆

void HPInitArray(HP* php, HPDataType* a, int n) {php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");return;}//拷贝数组的值到堆中memcpy(php->a, a, sizeof(HPDataType) * n);php->size = php->capacity = n;//向下调整建堆 O(N)for (int i = (php->size - 1 - 1) / 2; i >= 0; i--){AdjustDown(php->a, php->size, i);}}

我们先下调整的初始位置为最后一个子节点的父节点开始向下调整的。

向下调整的时间复杂度为：O(N)

#include"Heap.h"void HeapSort(HPDataType* a, int n) {//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//小堆降序  大堆升序int end = n - 1;while (end > 0){Swap(&a[0],&a[end]);AdjustDown(a, end, 0);end--;}}int main() {int a[] = { 20,17,5,3,4,16 };HeapSort(a, sizeof(a) / sizeof(a[0]));}

void CreateNdate()
{int n = 1000;//个数srand(time(0));FILE* fin = fopen("date.txt", "w");if (fin == NULL){perror("fopen fail");return;}int x = 0;for (int i = 0; i < n; i++){x = (rand() + i) % 10000000;fprintf(fin, "%d\n",x);}fclose(fin);
}

然后通过建堆比较来使得堆里元素为最大(或最小)

void tok() {int k = 0;printf("请输入k的值>");scanf("%d", &k);FILE* fout = fopen("date.txt", "r");if (fout == NULL){perror("fopen error");return;}int* minheap = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}//建一个k的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minheap, k, i);}int x = 0;//比较while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}fclose(fout);
}