二叉树中堆的数据结构

堆的概念和结构如果有一个关键码的集合K {k1 k2 k3 …kn }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中i为下标并满足ki k(2i1)且 ki k(2i2)(ki k(2i1) 且 kik(2i2) ) i 012…则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。堆的性质堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。下面是大堆的示例图堆的代码实现//堆的初始化voidHpInit(Hp*php){assert(php);php-aNULL;php-sizephp-capacity0;}//堆的销毁voidHpDestroy(Hp*php){assert(php);php-aNULL;php-sizephp-capacity0;}//交换函数voidSwap(int*p1,int*p2){inttmp*p1;*p1*p2;*p2tmp;}//向上调整voidAdjustUp(HpData*a,intchild){assert(a);intparent(child-1)/2;while(child0){if(a[child]a[parent]){Swap(a[child],a[parent]);childparent;parent(child-1)/2;}else{break;}}}//堆的插入向上调整版voidHpPush(Hp*php,HpData x){assert(php);if(php-capacityphp-size){intnewcapacityphp-capacity0?4:2*php-capacity;HpData*tmp(int*)realloc(php-a,newcapacity*sizeof(HpData));if(tmpNULL){perror(realloc fail!);return;}php-atmp;php-capacitynewcapacity;}php-a[php-size]x;php-size;AdjustUp(php-a,php-size-1);}// 堆数据的打印voidHpPrint(Hp*php){for(inti0;iphp-size;i){printf(%d ,php-a[i]);}printf(\n);}//向下调整voidAdjustDown(HpData*a,intparent,intsize){assert(a);intchild2*parent1;while(childsize){if(child1sizea[child]a[child1]){child;}if(a[child]a[parent]){Swap(a[child],a[parent]);parentchild;child2*parent1;}else{break;}}}//堆的插入向下调整版voidHpPush2(Hp*php,HpData x){assert(php);if(php-capacityphp-size){intnewcapacityphp-capacity0?4:2*php-capacity;HpData*tmp(int*)realloc(php-a,newcapacity*sizeof(HpData));if(tmpNULL){perror(realloc fail!);return;}php-atmp;php-capacitynewcapacity;}php-a[php-size]x;php-size;AdjustDown(php-a,0,php-size);}//判空boolHpEmpty(Hp*php){if(php-aNULL){returntrue;}else{returnfalse;}}//取堆顶数据HpDataHpTop(Hp*php){assert(php);returnphp-a[0];}//删除堆顶voidHpPop(Hp*php){Swap(php-a[0],php-a[php-size-1]);php-size--;AdjustDown(php-a,0,php-size);}堆排序通过上面的介绍我们已经了解了堆是如何实现的以及如何建立大堆和小堆所以接下来我们可以通过上面完成的向上和向下调整建堆来实现堆排序//向上调整建堆voidHpSort1(){intarr[]{4,6,1,7,9,8,2,5};//降序 先建小堆for(inti0;isizeof(arr)/sizeof(int);i){AdjustUp(arr,i);}intendsizeof(arr)/sizeof(int)-1;while(end0){Swap(arr[0],arr[end]);AdjustDown(arr,0,end);end--;}for(inti0;isizeof(arr)/sizeof(int);i){printf(%d ,arr[i]);}}//向下调整建堆voidHpSort2(){intarr[]{4,6,1,7,9,8,2,5};intnsizeof(arr)/sizeof(int);intendn;for(inti(n-1-1)/2;i0;i--){AdjustDown(arr,i,n);}while(end0){Swap(arr[0],arr[end-1]);AdjustDown(arr,0,end-1);--end;}for(inti0;isizeof(arr)/sizeof(int);i){printf(%d ,arr[i]);}}intmain(){HpSort1();printf(\n);HpSort2();return0;}我们这里实现的是降序排序代码解析首先我们两个代码都是进行建立小堆然后将堆顶最小的数与堆末尾的数据交换再进行向上或向下调整这样又把第二小的数放在了堆顶而我们使用了–end使得最小的数永远留在了堆末尾然后依次循环又不断地将次小的数据置在堆顶并与下标为end的数据交换再进行调整从而实现降序排序。注意事项向下调整建堆时间复杂度是 O (n)向上调整是 O (n log n)所以一般使用向下调整建堆向上调整建堆从第 0 个元素开始一个个插入堆每插入一个都要向上走到根最多走 树高 h log₂n总共 n 个节点复杂度O(n log n)向下调整建堆只调整非叶子节点从倒数第二层开始往前调越靠近底层的节点需要向下走的步数越少复杂度O(n)