php中emptyhp技巧_数据结构C措辞实现二叉树的介绍及堆的实现

假设树的高度是h,前h-1层是满的，末了一层不满，但是末了一层从左往右都是连续的。

末了一层最少有一个结点。

结点个数为:2^h-1-X= N,高度近似为:h = log2N+1+X以二为底N的对数+1

图有点丢脸不要介意

这些便是关于树的一些基本观点，下面我们来先容一下关于树的实现。

这里我们将会分为初始化、销毁、建堆、堆的删除、取出堆顶元素、判断是否为空、向上调度和向下调度这几步来完成。

#pragma once#include<stdio.h>#include<iostream>#include<stdlib.h>#include<assert.h>#include<algorithm>#include<cmath>#include<utility>typedef int HPDataType;typedef struct Heap{HPDataType a;int size;int capacity;}HP;初始化：

//初始化void HPInit(HP php){assert(php);php->a = NULL;php->capacity = php->size= 0;}销毁：

void HPDestroy(HP php){assert(php);free(php);php->a = NULL;php->capacity = php->size = 0;}向上调度：

//向上调度(小根堆)void AdjustUp(HPDataType a, int child){int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//小于就换就相称于建小堆//if (a[child] > a[parent])//大于就换就会变成大堆{std::swap(a[child], a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}建堆：

void HPPush(HP php, HPDataType x){assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity 2;HPDataType tmp = (HPDataType)realloc(php->a,sizeof(HPDataType) newcapacity);if (tmp == NULL){perror("realloc failed!!!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;//向上调度AdjustUp(php->a, php->size - 1);}向下调度：

void AdjustDown(HPDataType a, int n, int parent){//假设法//假设左孩子小int child = parent 2 + 1;while(child<n){if (child + 1 < n &&a[child + 1] < a[child])//这里如果是左孩子大于右孩子，就要再加加child{++child;}if (a[child] < a[parent]){std::swap(a[child], a[parent]);parent = child;child = parent 2 + 1;}else break;}}删除堆顶的数据：

HPDataType HPTop(HP php){assert(php);assert(php->size > 0);return php->a[0];}判空：

bool HPEmpty(HP php){assert(php);return php->size == 0;}总代码：TEST.c:

#include"Heap.h"void TestHeap1(){int a[] = { 4,2,8,1,5,6,7,9 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);}void HeapSort(int a, int n){//首先建堆//升序：建大堆//降序：建小堆for (int i=0;i<n;i++){AdjustUp(a, i);}int end = n - 1;///这里>0即可，由于=0时只剩下末了一个，就不再须要连续进行了while (end>0)//思路便是：比如我们升序排序，那么我们就利用大根堆，每次都将最大的那个数放在最顶上，然后将它和末了一个交流，然后让整体的大小--，那么末了一个就不再见受影响{std::swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}}void TestHeap2(){int a[] = { 4,2,8,1,5,6,9,7,3,10,23,14,125 };HeapSort(a, sizeof(a) / sizeof(0));for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){std::cout << a[i] << " ";}}int main(){TestHeap2();return 0;}Heap.c:

#include"Heap.h"//初始化void HPInit(HP php){assert(php);php->a = NULL;php->capacity = php->size= 0;}//销毁void HPDestroy(HP php){assert(php);free(php);php->a = NULL;php->capacity = php->size = 0;}//向上调度(小根堆)void AdjustUp(HPDataType a, int child){int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//小于就换就相称于建小堆//if (a[child] > a[parent])//大于就换就会变成大堆{std::swap(a[child], a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//建堆void HPPush(HP php, HPDataType x){assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity 2;HPDataType tmp = (HPDataType)realloc(php->a,sizeof(HPDataType) newcapacity);if (tmp == NULL){perror("realloc failed!!!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;//向上调度AdjustUp(php->a, php->size - 1);}//向下调度void AdjustDown(HPDataType a, int n, int parent){//假设法//假设左孩子小int child = parent 2 + 1;while(child<n){if (child + 1 < n &&a[child + 1] < a[child])//这里如果是左孩子大于右孩子，就要再加加child{++child;}if (a[child] < a[parent]){std::swap(a[child], a[parent]);parent = child;child = parent 2 + 1;}else break;}}//删除堆顶的数据void HPPop(HP php){assert(php);assert(php->size > 0);std::swap(php->a[0], php->a[php->size - 1]);//便是将第一个与末了一个换掉，然后将他们向下调度，php->size--;//直接size--删去末了一个元素AdjustDown(php->a, php->size, 0);}//取出堆顶数据HPDataType HPTop(HP php){assert(php);assert(php->size > 0);return php->a[0];}bool HPEmpty(HP php){assert(php);return php->size == 0;}Heap.h:

#pragma once#include<stdio.h>#include<iostream>#include<stdlib.h>#include<assert.h>#include<algorithm>#include<cmath>#include<utility>typedef int HPDataType;typedef struct Heap{HPDataType a;int size;int capacity;}HP;//初始化void HPInit(HP php);//销毁void HPDestroy(HP php);//建堆void HPPush(HP php,HPDataType x);//堆的删除void HPPop(HP php);//取出堆顶数据HPDataType HPTop(HP php);bool HPEmpty(HP php);void AdjustUp(HPDataType a, int child);void AdjustDown(HPDataType a, int n, int parent);