因此，树是递归定义的

前言

一、排版拙劣，望见谅。

因为向上调整算法建堆的时间复杂度是：O(N*logN)，而向下调整算法建堆的时间复杂度是：O(N)，所以我们优先使用向下调整算法建堆来实现堆排序。特殊的二叉树

• 满二叉树：一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。网络路由、概念和结构
• 2、

  ---

  4.2堆的实现

  堆的底层结构是数组，基本与顺序表一样。完整代码

  heap.h:

  #pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>typedefintHeapDataType;typedefstructHeap{HeapDataType*arr;intsize;intcapacity;}Heap;voidAdjustUp(HeapDataType*arr,intchild);voidAdjustDown(HeapDataType*arr,intparent,intn);voidSwap(HeapDataType*child,HeapDataType*parent);voidHeapInit(Heap*php);voidHeapDestroy(Heap*php);voidHeapPush(Heap*php,HeapDataType x);voidHeapPop(Heap*php);HeapDataType HeapTop(Heap*php);bool HeapEmpty(Heap*php);

  heap.c:

  #define_CRT_SECURE_NO_WARNINGS#include"heap.h"voidHeapInit(Heap*php){assert(php);php->arr =NULL;php->size =php->capacity =0;}voidHeapDestroy(Heap*php){assert(php);free(php->arr);php->arr =NULL;php->size =php->capacity =0;}voidSwap(HeapDataType*child,HeapDataType*parent){HeapDataType tmp =*child;*child =*parent;*parent =tmp;}voidAdjustUp(HeapDataType*arr,intchild){intparent =(child -1)/2;while(child >0){//  > 是建大堆if(arr[child]>arr[parent]){Swap(&arr[child],&arr[parent]);child =parent;parent =(child -1)/2;}else{break;}}}voidHeapPush(Heap*php,HeapDataType x){assert(php);if(php->size ==php->capacity){intnewcapacity =php->capacity ==0?4:2*php->capacity;HeapDataType*tmp =(HeapDataType*)realloc(php->arr,newcapacity *sizeof(HeapDataType));if(tmp ==NULL){perror("realloc fail");return;}php->arr =tmp;tmp =NULL;php->capacity =newcapacity;}php->arr[php->size]=x;php->size++;//向上调整AdjustUp(php->arr,php->size -1);}voidAdjustDown(HeapDataType*arr,intparent,intn){//假设左孩子小intchild =2*parent +1;while(child <n)//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 =2*parent +1;}else{break;}}}voidHeapPop(Heap*php){assert(php);assert(php->size >0);Swap(&php->arr[0],&php->arr[php->size -1]);php->size--;AdjustDown(php->arr,0,php->size);}HeapDataType HeapTop(Heap*php){assert(php);assert(php->size >0);returnphp->arr[0];}bool HeapEmpty(Heap*php){assert(php);returnphp->size ==0;}

  test.c:

  #define_CRT_SECURE_NO_WARNINGS#include"heap.h"voidtest1(){intarr[]={5,3,2,8,5,3,6,9,0};Heap hp;HeapInit(&hp);for(inti =0;i <sizeof(arr)/sizeof(int);i++){HeapPush(&hp,arr[i]);}HeapDestroy(&hp);}voidtest2(){//排升序intarr[]={5,3,2,8,5,3,6,9,0};for(inti =1;i <sizeof(arr)/sizeof(int);i++){//建大堆AdjustUp(arr,i);}}//void HeapSort(int* arr, int n)//{//	//升序，建大堆//	//降序，建小堆////	for (int i = 1; i < n; i++)//	{//		AdjustUp(arr, i);//}////	int end = n - 1;//	while (end > 0)//	{//		Swap(&arr[0], &arr[end]);//		AdjustDown(arr, 0, end);//		end--;//}//}voidTOP(){Heap hp;HeapInit(&hp);intarr[]={34,453,3,4,56,36,6,3,7,34,6,36,3,7,2,4,46,534,7,3,7673,56};for(inti =0;i <sizeof(arr)/sizeof(int);i++){HeapPush(&hp,arr[i]);}intk =0;scanf("%d",&k);while(k--){printf("%d ",HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);}intmain(){//test1();//test2();TOP();return0;}

  ---

  总结

  • 二叉树在各种领域和问题中都有广泛的应用，文件系统、
    因为小堆的堆顶是所有数里的最小值，此时堆顶已经排好了，要想排剩下的数就要重新建堆，这样一来父子关系全乱了，实现起来代价太大。

  ---

  4.3.2 TOP-K问题

  TOP-K问题：求数据量比较大的数据中前K个最大或最小的元素。

  假设父亲在数组中的下标为：i

  • 左孩子在数组中的下标：2*i+1
  • 右孩子在数组中的下标：2*i+2

  假设孩子在数组中的下标是：j

  • 父亲在数组中的下标就是(j-1）/ 2

  实际中常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆不是一回事，一个是数据结构，一个是操作系统中管理内存的一块区域划分。完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的，因此满二叉树是一种特殊的完全二叉树。世界企业TOP500、中国名校TOP100等。

  堆具有以下性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆是一棵完全二叉树

  其中堆又分为大堆和小堆：

  • 大堆 / 大根堆 / 大顶堆：任何一个父亲>=孩子，根最大
  • 小堆 / 小根堆 / 小顶堆：任何一个父亲<=孩子，根最小

  

  从上图中可以看到，小堆不一定是升序，大堆也不一定是降序，因为兄弟之间没有大小关系。在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关联。树的表示

• 4、因此定义堆的结构为：

  typedefintHeapDataType;typedefstructHeap{HeapDataType*arr;intsize;intcapacity;}Heap;voidHeapInit(Heap*php);voidHeapDestroy(Heap*php);HeapDataType HeapTop(Heap*php);bool HeapEmpty(Heap*php);

  其中初始化、二叉树的存储

  3.1顺序存储

  顺序存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，如果不是完全二叉树要保证下标对应就会有空间浪费，因此完全二叉树适合用顺序结构存储。从上图可以看到，二叉树有以下特点：

  二叉树的特点：

  • 二叉树不存在度大于2的节点
  • 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

  对于任意二叉树都是由以下几种情况复合而成的：

  

  ---

  2、

  

  向下调整：

  

  voidAdjustDown(HeapDataType*arr,intparent,intn){//假设左孩子小intchild =2*parent +1;while(child <n)//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 =2*parent +1;}else{break;}}}voidHeapPop(Heap*php){assert(php);assert(php->size >0);Swap(&php->arr[0],&php->arr[php->size -1]);php->size--;AdjustDown(php->arr,0,php->size);}

  向下调整算法建堆时间复杂度为：O(N)

  ---

  4.3堆的应用

  4.3.1堆排序

  | 版本一：基于已有数组建堆，取堆顶元素完成排序

  voidHeapSort(HeapDataType*arr,intn){Heap hp;for(inti =0;i <n;i++){HeapPush(&hp,arr[i]);}inti =0;while(!HeapEmpty(&hp)){arr[i++]=HeapTop(&hp);HeapPop(&hp);}HeapDestroy(&hp);}

  该版本有一个前提：必须提供有现成的数据结构堆。树形结构应用场景

  文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件好文件夹。

3、

---

二、

---

4、数据库、

//向上调整建堆for(inti =1;i <n;i++){AdjustUp(arr,i);}//向下调整建堆for(inti =(n-1-1)/2;i >=0;i--){AdjustDown(arr,i,n);}

向上调整算法建堆时默认第一个元素已经排好，从下标为1的元素往后依次开始调整。二叉树

1、
堆顶数据和最后一个数据交换再删除的目的是保证根节点下左右子树都是堆，父子关系不会乱。相关术语

树有很多的术语，基本都是根据现实中的树和人类亲缘关系命名的，其中红色标记的是比较重要的概念。

voidTOP(){Heap hp;HeapInit(&hp);intarr[]={34,453,3,4,56,36,6,3,7,34,6,36,3,7,2,4,46,534,7,3,7673,56};for(inti =0;i <sizeof(arr)/sizeof(int);i++){HeapPush(&hp,arr[i]);}intk =0;scanf("%d",&k);while(k--){printf("%d ",HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);}

---

5、