二叉树_堆的代码实现
1.二叉树实现堆的基本文件定义
1.头文件Heap.h
2.源文件Heap.c
3.测试文件test.c
2.二叉树实现堆的代码内容
代码内容:
//Heap.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//大根堆---父亲>孩子
//小根堆---父亲<孩子
//请记住堆的性质在学习代码
//我使用的是小堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
void HeapInit(HP* p);//初始化堆
void HeapDestory(HP* p);//销毁堆
void HeapPush(HP* p,HPDataType x);//插入堆
//不讲究头插尾插中间插问题
//因为如果这样插入不就是单链表插入了吗
//要满足二叉树的性质插入
void HeapPop(HP* p);//删除堆
void Swap(HPDataType* pa, HPDataType* pb);//向上向下调整交换数
void AdjustUp(HPDataType* a, size_t child);//向上调整数
void AdjustDown(HPDataType* a, size_t size,size_t root);//向下调整数 O(logN)
void HeapPrint(HP* p);//打印堆
bool HeapEmpty(HP* p);//堆是否为空
size_t HeapSize(HP* p);//堆的长度
HPDataType HeapTop(HP* p);//堆顶数据
void HeapSort(int* a, int size);//升序堆排序
//Heap.c
#include"Heap.h"
void HeapInit(HP* p)//初始化堆
{
assert(p);
p->a = NULL;
p->size = p->capacity = 0;
}
void HeapDestory(HP* p)//销毁堆
{
assert(p);
free(p->a);
p->a = NULL;
p->size = p->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)//向上向下调整交换数
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustDown(HPDataType* a, size_t size, size_t root)//向下调整
{
assert(a);
size_t parent = root;
size_t child = parent * 2 + 1;//左孩子
while (child < size)
{
//1.选出左右孩子中小的那个
if (child+1< size && a[child+1] < a[child])//考虑越界child+1<size
{
++child;//指向右孩子 否则指向左孩子
}
//2.如果孩子小于父亲，则交换,并继续向下调整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(HPDataType* a, size_t child)//向上调整数
{
assert(a);
size_t parent = (child - 1) / 2;
while (child>0)//child=0就结束了
{
//if(a[child]>a[parent])则为大堆排序
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1)/2;
}
else
{
break;//孩子比父亲大或者等
}
}
}
void HeapPush(HP* p, HPDataType x)//插入堆
{
assert(p);
if (p->size == p->capacity)//空间满了扩容
{
size_t newCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("ralloc failed\n");
exit(-1);
}
p->a = tmp;
p->capacity = newCapacity;
}
p->a[p->size] = x;
++p->size;
//算法逻辑思想是二叉树，物理操纵上是数组中数据
//向上调整，继续保持为小堆
AdjustUp(p->a,p->size-1);
}
void HeapPrint(HP* p)//打印堆
{
assert(p);
for (size_t i = 0; i < p->size; i++)
{
printf("%d ", p->a[i]);
}
printf("\n");
}
void HeapPop(HP* p)//删除堆 删除堆顶的数据
{
//小堆删除的是最小的数
//大堆删除的是最大的数
//我们常用的挪动数据覆盖的方法有问题
//挪动数据是O(N)
//堆结构破坏了，父子间关系全乱了
//方法：
//根与最后一个数据交换，删除最后一个数据
//向下调整数据
//log(N)
assert(p);
assert(p->size > 0);
Swap(&p->a[0], &p->a[p->size - 1]);
--p->size;
AdjustDown(p->a, p->size,0);
}
bool HeapEmpty(HP* p)//堆是否为空
{
assert(p);
return p->size == 0;
}
size_t HeapSize(HP* p)//堆的长度
{
assert(p);
return p->size;
}
HPDataType HeapTop(HP* p)//堆顶数据
{
assert(p);
assert(p->size > 0);
return p->a[0];
}
//扩展
//优化升序排序 优点:O(N*logN) 原来排序是O(N*N)
//缺点:空间复杂度O(N),还需要再优化
void HeapSort(int* a, int size)//堆排序
{
HP p;
HeapInit(&p);
for (int i = 0; i < size; ++i)
{
HeapPush(&p, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&p))
{
a[j] = HeapTop(&p);
j++;
HeapPop(&p);
}
HeapDestory(&p);
}
//test.c
#include"Heap.h"
int main()
{
HP hp;
printf("测试插入功能!\n");
HeapInit(&hp);
HeapPush(&hp, 1);
HeapPush(&hp, 5);
HeapPush(&hp, 0);
HeapPush(&hp, 8);
HeapPush(&hp, 3);
HeapPush(&hp, 9);
HeapPrint(&hp);
printf("测试删除功能!\n");
HeapPop(&hp);
HeapPrint(&hp);
HeapDestory(&hp);
printf("\n");
printf("测试堆排序升序!\n");
int a[] = { 4,2,7,8,5,1,0,6 };
HeapSort(a, sizeof(a)/sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{
printf("%d ", a[i]);
}
return 0;
}
3.二叉树实现堆的代码结果
4.优化的堆排序
//扩展
//优化升序排序 优点:O(N*logN) 原来排序是O(N*N)
//缺点:空间复杂度O(N),还需要再优化
void HeapSort(int* a, int size)//堆排序
{
HP p;
HeapInit(&p);
for (int i = 0; i < size; ++i)
{
HeapPush(&p, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&p))
{
a[j] = HeapTop(&p);
j++;
HeapPop(&p);
}
HeapDestory(&p);
}
对于我示例中这个8个元素的数组来说，这两个时间复杂度的差距可能不是很大，但对于海量数据来说，差距就起飞啦！
这个数据的差距可大的很呢!
从上面的解释，你应该能看出来，堆排序是挺优秀！
但是我们一般并不会写上面的代码，因为它需要另建一个堆来存放数据，空间复杂度是O(N)
所有我们一般都需要使用向上或向下调整使其成为一个堆来进行排序
