二叉树的顺序结构和实现
二叉树顺序结构
普通的二叉树不适合用数组来储存，因为可能会浪费大量空间，只有完全二叉树适合使用顺序结构储存，不会有像普通的二叉树浪费空间。现实中我们通常把堆使用顺序结构的数组来储存二叉树，需要注意，这个堆是一种数据结构，并不是操作系统中虚拟进程地址空间的堆。
堆的概念和结构
堆的性质：堆中的某个节点的值不大于或者不小其父节点的值。
堆总是一个完全二叉树。
堆的实现
堆的结构：
//堆的结构
typedef int HPDataType;typedef struct Heap
{HPDataType* a;//顺序结构指针int size; int capacity; //空间大小
}Heap;其实就跟顺序表一样的结构
初始化：
void HeapInit(Heap* php)
{php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4); //先开辟4个int大小的空间 不够再扩容if (php->a == NULL){perror("malloc fail");exit(-1);}php->size = 0; //每增加一个元素++php->capacity = 4;//初始空间记录
}插入数据：
//插入数据
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->size == php->capacity) //空间不够 扩容{HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * (php->capacity * 2));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity *= 2; }php->a[php->size++] = x; //插入元素AdJustUP(php->a, php->size - 1); // 排序
}以上步骤跟顺序表一样插入数据，最后一步则不同，首先需要建堆排序，这里建大堆；
子节点找父节点，子节点的下标减1后再除以2就可以找到父节点，以此向上递归对比。
parent = (child-1)/2;
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}void AdJustUP(HPDataType* a, int child) //向上排序
{int parent = (child - 1) / 2; //子节点的父亲是子节点下标-1后除2while (parent >= 0){if (a[parent] < a[child]) //子节点比父节点大 就交换{Swap(&a[child], &a[parent]);child = parent; //继续向上计算parent = (child - 1) / 2;}else{break;}}
}删除数据：
//判断是否为空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}
//删除数据
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php)); //判断堆不为空 才可以继续删除操作Swap(&php->a[0], &php->a[php->size - 1]); //将最大的根与堆最后一个节点交换php->size--; //size-- 数据减一AdJustDown(php->a, php->size, 0); //向下排序
}最后一个数据是小的，所以大根堆，还需要向下排序，找到剩余数据中最大的数当根。
向下对比需要找到该节点的孩子节点。
左孩子节点： parent*2 +1;
右孩子节点： parent*2 +2;
void AdJustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}获取堆中有效数据个数：
//获取堆中有效数据的个数
int HeapSize(Heap* php)
{assert(php);return php->size; //返回size就是有效个数
}获取堆顶数据：
//堆顶数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php)); return php->a[0]; //大根堆就是最大的数，小根堆就是最小的数
}删除开辟的空间：
//删除开辟的空间
void HeapDestroy(Heap* php)
{free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}堆的应用
堆排序
需要升序：建大堆
需要降序：建小堆
利用堆的思想排序
建堆和删堆都可以使用向下调整：
void heapsort(int * a, int n) //o(n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){adjustdown(a, n, i); }
}int main()
{int a[10] = { 9,2,5,6,1,8,4,0,7,3 };heapsort(a, 10);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}printf("\n");return 0;
} 
从最后一个父节点向下排序，一直到根。
Top_k问题
有100000个元素，找到前K个最大或者最小的元素
数据量如果非常大，排序就不可取。不过可以建一个K个元素的堆，然后建小堆，依次对比，比根大的就交换元素，然后向下排序。
尝试解决一下这个问题：
---------------------------------------------------------------------------------------------------------------------------------
void PrintTopk(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");exit(-1);}int* n = (int*)malloc(sizeof(n) * k);for (int i = 0; i < k; i++){fscanf(fout, "%d", &n[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdJustDown(n, k, i);}int num = 0;int ret = fscanf(fout, "%d", &num);while (ret != EOF){if (num > n[0]){Swap(&num, &n[0]);AdJustDown(n, k, 0);}ret = fscanf(fout, "%d", &num);}for (int i = 0; i < k; i++){printf("%d ", n[i]);}printf("\n");fclose(fout);
}void CreateTopk()
{srand((unsigned int)time(NULL));const char* filename = "test.txt";FILE* pfile = fopen(filename, "w");if (pfile == NULL){perror("fopen fail");exit(-1);}for (int i = 0; i < 10000; i++){int x = rand() % 10000;fprintf(pfile, "%d\n",x);}PrintTopk(filename, 50);fclose(pfile);
}int main()
{CreateTopk();return 0;
}