# 数据结构第五课 -----二叉树的代码实现

## 小知识

typedef int HDataType;
typedef struct Heap
{
HDataType* tree;
int size;
int capacity;
}Heap;


### 插入

//向上调整
{
int child = Hsize - 1;
int parent = (Hsize - 1 - 1) / 2;
while (child > 0)
{
if (tree[child] < tree[parent])
{
HDataType b = tree[child];
tree[child] = tree[parent];
tree[parent] = b;
child = parent;
parent = (child - 1) / 2;
}
else
return;
}
}
// 插入
void Heappush(Heap* obj, HDataType elemest)
{
//判断释放满
if (obj->size == obj->capacity)
{
obj->capacity = (obj->capacity == 0 ? 4 : obj->capacity * 2);
HDataType * tmp = realloc(obj->tree, sizeof(Heap) * obj->capacity);
if (tmp == NULL)
{
perror("realloc");
return;
}
obj->tree = tmp;
}
obj->tree[obj->size++] = elemest;
//开始检查是否大于父节点

}


// 删除 (删除根节点)
void HeapPop(Heap* obj)
{
assert(obj);
assert(obj->size > 0);
//两节点交换
HDataType elemest = obj->tree[0];
obj->tree[0] = obj->tree[obj->size - 1];
obj->tree[obj->size - 1] = elemest;
obj->size--;
//向下调整
int parent = 0;
int  child = parent * 2 + 1;
if (parent * 2 + 1 < obj->size && parent * 2 + 2 < obj->size &&  obj->tree[parent * 2 + 1] > obj->tree[parent * 2 + 2] )
{
child = parent * 2 + 2;
}
while (child < obj->size)
{

//判断孩子和父亲的大小
if (obj->tree[parent] > obj->tree[child])
{
//两节点交换
HDataType elemest = obj->tree[parent];
obj->tree[parent] = obj->tree[child];
obj->tree[child] = elemest;
parent = child;
}
else
break;
child = parent * 2 + 1;
if (parent * 2 + 1 < obj->size && parent * 2 + 2 < obj->size && obj->tree[parent * 2 + 1] > obj->tree[parent * 2 + 2])
{
child = parent * 2 + 2;
}

}

}


### 根节点

// 根
HDataType  HeapTop(Heap* obj)
{
assert(obj);
assert(obj->size > 0);
return obj->tree[0];
}


### 长度

// 长度
size_t HeapSize(Heap* obj)
{
assert(obj);
return obj->size;
}


### 是否为空

//是否为空
bool HeapEmpty(Heap* obj)
{
assert(obj);
return obj->size == 0;
}


## TOP-K问题

TOP-K问题： 即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

1.思路: 把N个数创建成大堆,然后pop K次

2.思路:

1.读取N个数的K个,创建一个K个数的小堆,

2.然后依次把剩下的N-K个数进行和堆顶比较,如果大于堆顶就顶替堆顶,然后向下调整形成小堆,

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void exchange(int *a, int *b)
{
int e = *a;
*a = *b;
*b = e;
}
void PrintTop(int n)
{
//创建一个n个数的小堆
FILE* pf = fopen("./test.txt", "r");
if (pf == NULL)
{
perror("fopen");
return 1;
}
int* Heap = (int*)malloc(sizeof(int) * n);
int i = 0;
for (i = 0; i < n; i++)
{
int elemest;
fscanf(pf, "%d", &elemest);
Heap[i] = elemest;
//向上调整
int child = i;
int parent = (child - 1) / 2;
while (child > 0)
{
if (Heap[child] < Heap[parent])
{
exchange(&Heap[child], &Heap[parent]);
}
else
break;
child = parent;
parent = (child - 1) / 2;

}

}
// 继续读取下面的数据
int ch = 0;
while ( fscanf(pf, "%d", &ch) != EOF)
{
if (ch <= Heap[0])
{
continue;
}
Heap[0] = ch;
//向下调整
int parent = 0;
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && Heap[child] > Heap[child + 1])
{
child += 1;
}
if (Heap[child] < Heap[parent])
exchange(&Heap[child], &Heap[parent]);
else
break;
parent = child;
child = parent * 2 + 1;
}

}
//打印数据
for (i = 0; i < n; i++)
{
printf("%d ", Heap[i]);
}
free(Heap);
fclose(pf);
}
void random(int n)
{
FILE* pf = fopen("./test.txt", "w");
if (pf == NULL)
{
perror("fopen");
return 1;
}
srand(time(NULL));
int i = 0;
for (i = 0; i < 10000; i++)
{
fprintf(pf, "%d\n", (rand() + i) % 100000);
}

fclose(pf);
}

int main()
{
int n = 10;

PrintTop(n);

return 0;
}



// 第二种方法
//从最后一个节点的父亲开始向下调整,我们创建的是小堆 ,
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
//向下调整
int parent = i;
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && Heap[child] > Heap[child + 1])
{
child += 1;
}
if (Heap[child] < Heap[parent])
exchange(&Heap[child], &Heap[parent]);
else
break;
parent = child;
child = parent * 2 + 1;
}
}


## 堆排序

#include<stdio.h>
typedef int Heapdata;
void exchange(Heapdata *a, Heapdata *b)
{
Heapdata e = *a;
*a = *b;
*b = e;
}
void Heapsort(Heapdata* heap, int size)
{
//建大堆
int i = 0;
for (i = 1; i < size; i++)
{
//向上调整
int child = i;
int parent = (child - 1) / 2;
while (child > 0)
{
if (heap[child] > heap[parent])
{
//交换
exchange(&heap[child], &heap[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}

}
//开始升序排序
while (size > 0)
{
// 根节点和最后一个叶节点交换
exchange(&heap[0], &heap[--size]);
//向下调整
int parent = 0;
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && heap[child] < heap[child + 1])
{
child += 1;
}
if (heap[child] > heap[parent])
exchange(&heap[child], &heap[parent]);
else
break;
parent = child;
child = parent * 2 + 1;
}
}

}
int main()
{
Heapdata a[] = { 2,1,48,5,2,4,7,5,63,8 };
int size = sizeof(a) / sizeof(a[0]);
//堆排序
Heapsort(a, size);

return 0;
}


## 总结

|
15天前
|

【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能，助你提升算法效率。堆用于快速找大数据集的第K大元素，如示例所示，时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务，如模拟下载管理器，按优先级处理任务。掌握这些工具，让代码运行更高效！
37 1
|
28天前
|

【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
17 0
|
28天前
|

【数据结构和算法】---二叉树（1）--树概念及结构
【数据结构和算法】---二叉树（1）--树概念及结构
18 0
|
4天前
|

【数据结构】树和二叉树的概念及结构

23 3
|
7天前
|

【7月更文挑战第16天】并查集，Python中的效率明星，处理不相交集合合并与查询。用于社交网络分析、图像处理、图论算法等领域。优雅实现结合路径压缩和按秩合并
11 1
|
28天前
【数据结构】判断二叉树是否是完全二叉树
【数据结构】判断二叉树是否是完全二叉树
17 5
|
28天前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
22 5
|
28天前
|

【数据结构】手把手分析：链式二叉树的实现
【数据结构】手把手分析：链式二叉树的实现
21 5
|
28天前
|

【数据结构和算法】--- 二叉树（5）--二叉树OJ题
【数据结构和算法】--- 二叉树（5）--二叉树OJ题
16 1
|
15天前
|

【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能，用于高效数据管理。堆是完全二叉树，heapq实现最小堆，常用于任务调度，如按优先级执行任务。当需要线程安全且更复杂操作时，queue.PriorityQueue成为优选，例如在管理网络请求时按优先级处理。这两个数据结构能提升代码效率和可读性。
14 0