4.堆的实现
这里我们用数组来实现。
先定义一个结构体：
typedef int HeapDatatype; typedef struct Heap { HeapDatatype* a; int size; int capacity; }HP;
初始化堆
void HeapInit(HP* php) { php->a = (HeapDatatype*)malloc(4*sizeof(HeapDatatype)); if (php->a == NULL) { perror("malloc fail\n"); return; } php->size = 0; php->capacity = 4; }
堆的插入
void HeapPush(HP* php, HeapDatatype x) { if (php->size == php->capacity) { HeapDatatype* tmp = (HeapDatatype*)realloc(php->a, sizeof(HeapDatatype) * (php->capacity) * 2); if (tmp == NULL) { perror("realloc fail\n"); return; } php->a = tmp; php->capacity *= 2; } php->a[php->size] = x; php->size++; AdjustDwon(php->a, php->size-1); }
向上调整法
堆要么是大堆，树的任意一个父节点都大于等于子节点，要么是小堆，树的任意一个父亲都小于等于孩子，所以我们每插入一个数据都要和它的父亲进行比较，这里使用向上调整法：
假设我们要得小堆，那每当插入的孩子小于父亲时都要交换它们的位置，前文我们讲了，可以通过孩子的下标找到父亲，再把父亲的下标给孩子，直到孩子是根节点或者中途父亲就已经小于孩子，就停止循环（如果要得到大堆，当插入的孩子大于父亲时交换它们的位置）。
void AdjustUp(HeapDatatype*a,int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[parent] > a[child]) { HeapDatatype p = a[parent]; a[parent] = a[child]; a[child] = p; child = parent; parent = (child - 1) / 2; } else { break; } } }
堆的删除
删除有两种方法：
1. 直接删除根节点，然后把剩下的节点重新生成堆。
2. 删除堆顶元素，然后把最后一个元素放到堆顶，然后使用向下调整法，直到满足堆的性质。
第一种方法过于复杂，我们采用第二种方法。
void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); swap(&php->a[0],&php->a[php->size-1]); php->size--; AdjustDown(php->a, php->size,0); }
向下调整法
具体步骤如下：
我们可以通过child=parent*2+1和child=parent*2+2得到父节点的左右子节点，然后从堆顶开始，将堆顶元素与其左右子节点中较小的那个进行比较，如果堆顶元素小于其子节点中的较小值，则将其与较小值交换位置，并继续向下比较，直到堆的性质被满足（如果要得到大堆就与较大的那个进行比较，如果堆顶元素大于子节点中的较大值，则将其和较大值交换位置）
代码如下：
void AdjustDown(HeapDatatype*a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] > a[child + 1]) { child++; } if (a[parent] > a[child]) { swap(&a[parent],&a[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
函数swap()用来交换两个数的值：
swap(HeapDatatype* p1, HeapDatatype* p2) { HeapDatatype tmp = *p1; *p1 = *p2; *p2 = tmp; }
取堆顶的数据
堆顶数据就是数组中下标为0的数据。
代码如下：
HeapDatatype HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; }
堆的数据个数
int HeapSize(HP* php) { assert(php); return php->size; }
堆的判空
bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
堆的销毁
void HeapDestory(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = 0; php->capacity = 0; }
完整代码：
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" int main() { HP hp; HeapInit(&hp); int arr[] = { 65,100,70,32,50,60 }; int i = 0; for (i = 0; i < sizeof(arr) / sizeof(int); i++) { HeapPush(&hp, arr[i]); } while (!HeapEmpty(&hp)) { HeapDatatype top = HeapTop(&hp); printf("%d ", top); HeapPop(&hp); } return 0; }
Heap.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HeapDatatype; typedef struct Heap { HeapDatatype* a; int size; int capacity; }HP; //堆的初始化 void HeapInit(HP* php); //堆的销毁 void HeapDestory(HP* php); //堆的插入 void HeapPush(HP* php,HeapDatatype x); //堆的删除 void HeapPop(HP* php); //取堆顶元素 HeapDatatype HeapTop(HP* php); //堆中数据个数 int HeapSize(HP* php); //堆的判空 bool HeapEmpty(HP* php); //向上调整法 void AdjustUp(HeapDatatype* a, int child); //向下调整法 void AdjustDown(HeapDatatype* a, int n, int parent);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" //堆的初始化 void HeapInit(HP* php) { php->a = (HeapDatatype*)malloc(4*sizeof(HeapDatatype)); if (php->a == NULL) { perror("malloc fail\n"); return; } php->size = 0; php->capacity = 4; } //堆的销毁 void HeapDestory(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = 0; php->capacity = 0; } //交换两数值 swap(HeapDatatype* p1, HeapDatatype* p2) { HeapDatatype tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整法 void AdjustUp(HeapDatatype*a,int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[parent] > a[child]) { swap(&a[parent],&a[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //堆的插入 void HeapPush(HP* php, HeapDatatype x) { if (php->size == php->capacity) { HeapDatatype* tmp = (HeapDatatype*)realloc(php->a, sizeof(HeapDatatype) * (php->capacity) * 2); if (tmp == NULL) { perror("realloc fail\n"); return; } php->a = tmp; php->capacity *= 2; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size-1); } //向下调整法 void AdjustDown(HeapDatatype*a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] > a[child + 1]) { child++; } if (a[parent] > a[child]) { swap(&a[parent],&a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆的判空 bool HeapEmpty(HP* php) { assert(php); return php->size == 0; } //堆的删除 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); swap(&php->a[0],&php->a[php->size-1]); php->size--; AdjustDown(php->a, php->size,0); } //取堆顶元素 HeapDatatype HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; } //堆的数据个数 int HeapSize(HP* php) { assert(php); return php->size; }
测试：
我们要得到的是小堆，通过调试可以看到，堆中的元素依次是 32 50 60 100 65 70
很明显，满足小堆的性质。
我们再来打印一下堆顶元素，
每次pop后再打印堆顶元素出来，数据是升序，那说明堆可以实现数据的排序，那我们用堆排序每次都要写一个堆出来吗，那岂不是太麻烦了？
下节我们再来详细讲解堆排序及相关问题，未完待续。。。
