欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 社会 > 二叉树的顺序结构和实现---堆(Heap)

二叉树的顺序结构和实现---堆(Heap)

2024/12/22 1:12:32 来源:https://blog.csdn.net/sid_Tang/article/details/144279147  浏览:    关键词:二叉树的顺序结构和实现---堆(Heap)

二叉树的顺序结构和实现

二叉树顺序结构

普通的二叉树不适合用数组来储存,因为可能会浪费大量空间,只有完全二叉树适合使用顺序结构储存,不会有像普通的二叉树浪费空间。现实中我们通常把使用顺序结构的数组来储存二叉树,需要注意,这个堆是一种数据结构并不是操作系统中虚拟进程地址空间的堆

堆的概念和结构

堆的性质:堆中的某个节点的值不大于或者不小其父节点的值

                  堆总是一个完全二叉树。

堆的实现

堆的结构:

//堆的结构
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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com