C学习（数据结构）--＞ 实现顺序结构二叉树
目录
一、堆的概念与结构
性质
二叉树的性质
二、堆的实现
1、结构
2、初始化与销毁
3、入堆与出堆（小堆）
1）Swap
2）入堆
1 数据的向上调整
2 入堆
3）出堆
1 数据的向下调整
2 出堆
三、其他
1、入堆与出堆（大堆）
2、堆排序
1）排降序
2）排升序
3、Top-K问题
四、总代码
Heap.h
Heap.cpp
main.cpp
一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树。具有二叉树的特性的同时，还具有其它的特性。
一、堆的概念与结构
如果有一个集合，把它所有的元素按完全二叉树的顺序存储方式存储，在一维数组中，并且每一个父节点小于它的孩子结点，则称这个完全二叉树为小堆，而称每一个父节点大于它的孩子结点的完全二叉树为大堆。
- 小堆
- 大堆
性质
根据以上可得，堆总是一棵完全二叉树，且堆中某个结点的值总是不大于或不小于父结点的值。
二叉树的性质
对于一个完全二叉树，按照从上至下从左至右的数组顺序对所有结点从0开始编号，那么对于序号为 i 的结点（i - 1）/ 2 对应的结点是它的父结点，2*i + 1 对应的结点是它的左孩子结点，2*i + 2 对应的结点是它的父结点
二、堆的实现
1、结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;2、初始化与销毁
//堆的初始化
void HPInit(Heap* php)
{assert(php);php->arr = NULL;php->capacity = php->size = NULL;
}//堆的销毁
void HPDestroy(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = NULL;
}3、入堆与出堆（小堆）
1）Swap
通过Swap函数交换两个数据
//两个数据的交换
void Swap(HPDataType* x, HPDataType* y)
{assert(x || y);HPDataType cpy = *x;*x = *y;*y = cpy;
}2）入堆
1 数据的向上调整
//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] < arr[parent])//当孩子结点小于父节点时，两个数据交换{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}2 入堆
//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpSmall(php->arr, php->size++);
}
3）出堆
1 数据的向下调整
//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] > arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}2 出堆
//出堆(小堆)
void HPPopSmall(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownSmall(php->arr, 0, php->size);
}三、其他
1、入堆与出堆（大堆）
与小堆大同小异
//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpBig(php->arr, php->size++);
}//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] < arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(大堆)
void HPPopBig(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownBig(php->arr, 0, php->size);
}
2、堆排序
1）排降序
以排降序为例，通过建小堆来实现堆排序
void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{// //向上建堆// AdjustUpSmall(arr, i);//}//向下排序，建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0)//出堆{Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}2）排升序
同理，通过建立大堆排升序
void HeapSortBig(int* arr, int n)
{//向下排序，建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}3、Top-K问题
- 问：有一个数据量特别大的集合，如何用一个最多包含 K 个元素的集合来求得最大或最小的前 K 个元素
- 答：用前 K 个元素建大堆或小堆，在用剩余的N-K个元素依此与堆顶元素比较大小，如过该元素比堆顶元素大于或小于，则替换掉堆顶元素。
//造数据
void CreateNDate()
{int n = 100000;srand((unsigned int)time(NULL));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!!!");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//Top-K 问题
void TopK()
{int k = 10;const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!!!");exit(1);}int minHeap[10] = { 0 };//从文件中读前K个数据for (int i = 0; i < k; i++){fscanf(fout, "&d\n", minHeap);}//建小堆for (int i = (k - 1 - 1) / 2; i > 0; i--){AdjustDownSmall(minHeap, 0, k);}//继续取文件的数据，将读取到的数据和堆顶进行比较int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDownSmall(minHeap, 0, k);}}//排升序printf("排升序：");HeapSortBig(minHeap, 10);for (int i = 0; i < 10; i++){printf("%d ", minHeap[i]);}printf("\n");fclose(fout);
}四、总代码
Heap.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;
//堆的初始化
void HPInit(Heap* php);
//堆的销毁
void HPDestroy(Heap* php);
//两个数据的交换
void Swap(HPDataType* x, HPDataType* y);
//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child);
//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x);
//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n);
//出堆(小堆)
void HPPopSmall(Heap* php);
//判空
bool HPEmpty(Heap* php);
//取堆顶数据
HPDataType HPTop(Heap* php);
//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child);
//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x);
//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n);
//出堆(大堆)
void HPPopBig(Heap* php);
//堆排序
//排升序，建大堆
//排降序，建小堆
void HeapSortSmall(int* arr, int n);
void HeapSortBig(int* arr, int n);Heap.cpp
#include"Heap.h"//堆的初始化
void HPInit(Heap* php)
{assert(php);php->arr = NULL;php->capacity = php->size = NULL;
}//堆的销毁
void HPDestroy(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = NULL;
}//两个数据的交换
void Swap(HPDataType* x, HPDataType* y)
{assert(x || y);HPDataType cpy = *x;*x = *y;*y = cpy;
}//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpSmall(php->arr, php->size++);
}//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] > arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(小堆)
void HPPopSmall(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownSmall(php->arr, 0, php->size);
}//判空
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}//取堆顶数据
HPDataType HPTop(Heap* php)
{assert(php && php->size);return php->arr[0];
}//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpBig(php->arr, php->size++);
}//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] < arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(大堆)
void HPPopBig(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownBig(php->arr, 0, php->size);
}//堆排序
//排升序，建大堆
//排降序，建小堆void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{// //向上建堆// AdjustUpSmall(arr, i);//}//向下排序for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}
void HeapSortBig(int* arr, int n)
{//向下排序for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}main.cpp
#include"Heap.h"//造数据
void CreateNDate()
{int n = 100000;srand((unsigned int)time(NULL));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!!!");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//Top-K 问题
void TopK()
{int k = 10;const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!!!");exit(1);}int minHeap[10] = { 0 };//从文件中读前K个数据for (int i = 0; i < k; i++){fscanf(fout, "&d\n", minHeap);}//建小堆for (int i = (k - 1 - 1) / 2; i > 0; i--){AdjustDownSmall(minHeap, 0, k);}//继续取文件的数据，将读取到的数据和堆顶进行比较int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDownSmall(minHeap, 0, k);}}//排升序printf("排升序：");HeapSortBig(minHeap, 10);for (int i = 0; i < 10; i++){printf("%d ", minHeap[i]);}printf("\n");fclose(fout);
}void test01()
{Heap hpsmall;//堆的初始化HPInit(&hpsmall);//入堆(小堆)HPDataType arr[10] = { 32,11,55,223,86,123,867,3423,75,13 };for (int i = 0; i < 10; i++){HPPushSmall(&hpsmall, arr[i]);}//取堆顶数据printf("Heap: ");while (!HPEmpty(&hpsmall)){printf("%d ", HPTop(&hpsmall));//出堆(小堆)HPPopSmall(&hpsmall);}printf("\n");//堆的销毁HPDestroy(&hpsmall);//排降序printf("排降序：");HeapSortSmall(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");//排升序printf("排升序：");HeapSortBig(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");//CreateNDate();TopK();
}int main()
{test01();return 0;
}