3.3.6堆的代码实现
定义类型和结构体
typedef int Datatype; typedef struct Heap { Datatype* a;//创建数组存储元素 Datatype size;//计算元素个数 Datatype capacity;//堆的容量 }Heap;
初始化堆
//初始化堆 void Heapinit(Heap* hp); void Heapinit(Heap* hp) { assert(hp); hp->a = NULL; hp->size = hp->capacity = 0; }
销毁堆
//销毁堆 void Heapdestory(Heap* hp); void Heapdestory(Heap* hp) { assert(hp); free(hp->a); hp->a = NULL; hp->size = hp->capacity = 0; }
插入数据
由上面堆的插入可知，数据从数组的末尾插入，然后进行向上调整，直到构建新的堆
由于交换元素在堆的其他功能中也会使用，为了方便就将其独立为函数
交换元素
void Swap(Datatype* p1, Datatype* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; }
//插入数据 void Heappush(Heap* hp, Datatype x); void Adjustup(Datatype* a, Datatype child) { assert(a); 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(Heap* hp, Datatype x) { assert(hp); //判断容量 if (hp->size == hp->capacity) { int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity; Datatype* tmp = (Datatype*)realloc(hp->a, newcapacity * sizeof(Datatype)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } hp->capacity = newcapacity; hp->a = tmp; } hp->a[hp->size] = x; hp->size++; //向上调整 Adjustup(hp->a, hp->size - 1); }
将数据 5，4，8，2，9，10，7 插入堆中，经过向上调整最终变成小根堆
小根堆
打印堆
//打印堆 void Heapprint(Heap* hp); void Heapprint(Heap* hp) { assert(hp); assert(!Heapempty(hp)); int i = 0; for (i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); } printf("\n"); }
读取堆顶数据
//读取堆顶数据 Datatype Heaptop(Heap* hp); //读取堆顶数据 Datatype Heaptop(Heap* hp) { assert(hp); assert(!Heapempty(hp)); return hp->a[0]; }
删除堆顶数据
//删除堆顶数据 void Heappop(Heap* hp); void Adjustdown(Datatype* a, int n, int parent) { assert(a); int minchild = parent * 2 + 1; while (minchild < n) { if (minchild + 1 < n && a[minchild+1] < a[minchild]) { minchild++; } if (a[minchild] < a[parent]) { Swap(&a[minchild], &a[parent]); parent = minchild; minchild = parent * 2 + 1; } else { break; } } } void Heappop(Heap* hp) { assert(hp); assert(!Heapempty(hp)); Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; //向下调整 Adjustdown(hp->a, hp->size, 0); }
判断堆是否为空
//判断堆是否为空 bool Heapempty(Heap* hp); bool Heapempty(Heap* hp) { assert(hp); return hp->size == 0; }
计算堆中的元素的个数
//计算堆中的元素的个数 int Heapsize(Heap* hp); int Heapsize(Heap* hp) { assert(hp); return hp->size; }
以上是通过将数组中的值传到堆中，再进行堆的调整，最后变为大根堆或小根堆
那么可不可以直接在数组中建堆，再进行调整，最终变为大根堆或小根堆呢？
答案是：当然可以
利用向上调整算法或者向下调整算法直接再数组中建堆，最终变为大根堆或者小根堆
代码实现如下
向上调整建堆
void HeapCreat(int* a, int n) { int i = 0; //向上建堆 for (i = 1; i < n; i++) { Adjustup(a, i); } } int main() { Heap hp; int arr[] = { 5,4,8,2,9,10,7 }; int sz = sizeof(arr) / sizeof(arr[0]); HeapCreat(arr, sz); return 0; }
向上建堆时间复杂度计算
调整次数=每层节点个数*每层向下调整的次数（最坏情况下，全部调整）
T(N)=2^1* 1 + 2^2 * 2+ 2^3* 3+…+2^(h-1) *(h-1)
2^h -1 = N h=log(N+1)
估算T(N) = N*log(N)
向下调整
根据上面介绍的思路，代码实现如下
void HeapCreat(int* a, int n) { int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i++) { Adjustdown(a, i); } } int main() { Heap hp; int arr[] = { 5,4,8,2,9,10,7 }; int sz = sizeof(arr) / sizeof(arr[0]); HeapCreat(arr, sz); return 0; }
3.4堆的应用
3.4.1堆排序
堆排序便是利用堆的特点进行排序，分为两个步骤
1.建堆
升序：建大堆 降序：建小堆
2.通过堆删除的思路进行排序
升序
建大堆
把最后一个节点和第一个节点交换，不把最后一个节点看作堆中。开始开始向下调整，选出次大的元素，依次类推
代码实现
void HeapCreat(int* a, int n) { int i = 0; //向下建堆 建大堆 for (i = (n - 1 - 1) / 2; i >= 0; --i) { Adjustdown(a, n, i); } i = 1; while (i < n) { 交换第一个和最后一个节点 Swap(&a[0], &a[n - i]); 重新向下调整 Adjustdown(a, n-i, 0); ++i; } } int main() { int arr[] = { 5,4,8,2,9,10,7 }; int sz = sizeof(arr) / sizeof(arr[0]); HeapCreat(arr, sz); int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
降序的思路与升序的思路类似，这里就不加赘叙
3.4.2TOP-K问题
求得数据集合中前K个最大或者最小的元素
方法：
- 排序 时间复杂度 O(N*logN)
- 建堆->堆排序
当数据集合特别大时，方法1便不可行，数据太大不能在堆上存储数据，只能在磁盘上存储数据。
所以采取方法2
方法2也有两种方式去实现
建大堆 建N个数的大堆，再popK次即可
建小堆，建K个数的小堆，依次遍历后(N-K)个数，如果比堆顶的数据大，便进行交换，再向下调整即可
代码实现 建小堆
void Creatflie(const char* file, int N) { FILE* fin = fopen("test.txt", "w"); if (fin == NULL) { perror("fopen fail"); exit(-1); } srand((unsigned int)time(0)); int i = 0; for (i = 0; i < N; i++) { fprintf(fin, "%d\n", rand() % 10); } fclose(fin); } void Printtopk(const char* file, int k) { assert(file); FILE* fout = fopen("test.txt", "r"); if (fout == NULL) { perror("fopen fail"); exit(-1); } int* minHeap = (int*)malloc(k * sizeof(int)); if (minHeap == NULL) { perror("malloc fail"); exit(-1); } int i = 0; //读取前k个元素 for (i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //建k个数的小根堆 for (i = (k - 2) / 2; i < k; i++) { Adjustdown(minHeap, k, i); } //读取N-K个数 int val = 0; while (fscanf(fout, "%d", &val) != EOF) { if (val > minHeap[0]) { minHeap[0] = val; Adjustdown(minHeap, k, 0); } } for (i = 0; i < k; i++) { printf("%d ", minHeap[i]); } printf("\n"); free(minHeap); fclose(fout); } int main() { const char* file = "test.txt"; int N = 10; int k = 5; //创建文件 Creatflie(file, N); Printtopk(file, k); return 0; }
4.二叉树的链式结构及实现
4.1前置说明
二叉树
空树
非空：根节点，根节点的左子树，根节点的右子树组成
4.2二叉树的遍历
4.2.1前序，中序以及后序遍历
二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
二叉树的遍历有三种方式：前序/中序/后序递归遍历
前序遍历：最先访问根节点，其次访问左子树，右子树
中序遍历：最先访问左子树，其次访问根，右子树
后序遍历：最先访问左子树，其次访问右子树，根
前序遍历
void Preorder(BTnode* root) { if (root == NULL) { printf("NULL "); return; } assert(root); printf("%d ", root->data); Preorder(root->left); Preorder(root->right); }
对上面的二叉树进行前序遍历
运行结果与上述分析一致
中序遍历
void Inorder(BTnode* root) { if (root == NULL) { printf("NULL "); return; } assert(root); Inorder(root->left); printf("%d ", root->data); Inorder(root->right); }
对上面的二叉树进行中序遍历
运行结果与上述分析一致
后序遍历
void Postorder(BTnode* root) { if (root == NULL) { printf("NULL "); return; } assert(root); Postorder(root->left); Postorder(root->right); printf("%d ", root->data); }
对上面的二叉树进行后序遍历
运行结果与上述分析一致
