树--二叉树--堆

本节目标

简单了解树，二叉树，堆的概念

认识堆这个数据结构

堆排序，topk问题

一、树的概念及结构

1.树的概念

在现实生活中，树是随处可见的，如下图,那么数据结构中的树是什么样的？

数据结构中的“树”看起来像是一颗倒挂的树，根在最上面，向下生长，形成许多分支。

树的定义：

树是一种非线性的数据结构，由节点（或称为顶点）和边组成，具有以下特性：

2.树的相关术语

树的基本术语

节点（Node）：树中的每个元素称为节点，包含数据项及指向其他节点的分支。

根节点（Root）：树的顶层节点，没有父节点，是整棵树的起点。

父节点（Parent）：一个节点的直接上层节点称为其父节点。

子节点（Child）：一个节点的直接下层节点称为其子节点。

叶节点（Leaf）：没有子节点的节点，位于树的末端。

内部节点（Internal Node）：至少有一个子节点的非根节点。

树的层级与关系

度（Degree）：一个节点拥有的子节点数量称为该节点的度。

树的度（Tree Degree）：树中所有节点的度的最大值。

层次（Level）：根节点为第1层（或第0层，取决于定义），其子节点为第2层，以此类推。

高度（Height）：从某节点到其最远叶节点的最长路径边数。树的高度即根节点的高度。

深度（Depth）：从根节点到某节点的路径边数。根节点的深度为0（或1）。

3.树的分类

树可以根据其特性分为多种类型，包括二叉树、满二叉树、完全二叉树、二叉搜索树和平衡二叉树等。下面我们将重点介绍前三种类型。

1.二叉树

二叉树概念：二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。事实上，任意二叉树的构成为以下几种情况：

2.满二叉树和完全二叉树

满二叉树概念和性质：

满二叉树是一种特殊的二叉树结构，其特点是每一层的节点都达到最大数量。具体定义为：

• 所有非叶子节点都有两个子节点（左子节点和右子节点）。
• 所有叶子节点都位于同一层。
• 若满二叉树的深度为 ( h )（根节点深度为 1），则其总节点数为：
  [ N = 2^k – 1 ]
• 叶子节点数为 ( 2^{h-1} )

完全二叉树概念和性质：

完全二叉树是二叉树的一种特殊形式，满足以下条件：

对于满二叉树和完全二叉树：若从根节点开始，按照从上到下，从左到右的顺序从0开始编号，则对序号为i的节点有：(树有n个节点)

二、堆

二叉树的存储结构

二叉树一般可以使用两种方式来存储，顺序结构以及链式结构

1.顺序存储

顺序存储是指将二叉树每个节点按顺序存储到数组中，完全二叉树按照存储的顺序，能够找到其父节点或子节点，也能够高效利用空间。而非完全二叉树则会浪费一定的空间。

2.链式存储

链式存储通过节点对象和指针来实现，每个节点包含数据域和左右子节点指针。适用于任意形态的二叉树，空间利用率灵活。链式存储将在后续博客中讲解。

堆的概念和实现

普通的二叉树用数组实现会造成空间浪费，而完全二叉树则非常适合用数组来存储，现实中我们通常把堆（一种完全二叉树）使用数组来存储。

堆的概念

堆是一种特殊的完全二叉树结构，其每个节点的值都遵循特定的顺序关系。具体来说，堆可以分为两种主要类型：

堆的存储通常使用数组实现，利用完全二叉树的性质可以高效地进行节点定位：

• 对于任意节点i（从0开始计数）：
  • 父节点位置：(i-1)/2
  • 左子节点位置：2i+1
  • 右子节点位置：2i+2

堆的一个重要特性是：对于一个包含n个元素的堆，其高度为⌊log₂n⌋，这使得堆的各种操作都能保持较好的时间复杂度。在构建堆时，可以采用自底向上的堆化方法，时间复杂度为O(n)。

堆的实现

1.Heap.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int HPDataType;

typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//初始化，销毁
void HeapInit(HP* php);
void HeapDestroy(HP* php);
//插入删除
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
//取堆顶
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//调整
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);

2.Heap.c文件

#include "Heap.h"

void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

void HeapInit(HP* php)
{
assert(php);

php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)
{
assert(php);

free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}

void AdjustUp(HPDataType* a, int child)
{
int parent = (child – 1) / 2;
while (child > 0)
{
if (a[child] < a[parent]) //<是小堆，>是大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}
}
}

void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;

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] > a[child + 1]) //看建小堆还是大堆，改变符号
{
child++;
}

if (a[child] < a[parent]) //看建小堆还是大堆，改变符号
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}

}

void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);

Swap(&php->a[0], &php->a[php->size – 1]);
php->size–;

AdjustDown(php->a, php->size, 0);
}

//取堆顶
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);

return php->a[0];
}
//判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

堆的调整算法

向上调整算法

在插入新节点时，首先确定该节点的位置，然后将其数据与父节点进行比较。如果是小堆结构且新节点的数据小于父节点数据，则交换两者的位置，并将父节点序号赋给子节点。重复这一比较过程直至满足条件（child > 0）。(大堆类似）

void AdjustUp(HPDataType* a, int child)
{
int parent = (child – 1) / 2;
while (child > 0)
{
if (a[child] < a[parent]) //<是小堆，>是大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}
}
}

向下调整算法

将该节点数据与子节点进行比较 ，如果是小堆且该节点的数据大于子节点数据，则交换两者的位置，并将子节点序号赋给父节点，重复这一比较过程直至满足条件（child < n）

void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;

while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1]) //看建小堆还是大堆，改变符号
{
child++;
}

if (a[child] < a[parent]) //看建小堆还是大堆，改变符号
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}

}

建堆

向上调整建堆及其时间复杂度分析

int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };
HP hp;
HeapInit(&hp);
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HeapPush(&hp, a[i]);
}

向下调整建堆及其时间复杂度分析

for (int i = (n-1-1)/2; i >=0; i–)
{
AdjustDown(a, n, i);
}

向上调整与向下调整算法，实际上是不同的层数的调整次数不同，向上调整算法是节点多*调整次数多，向下调整算法是节点多*调整次数少，所以向下调整算法更好。

堆排序

堆排序的时间复杂度是 O(n log n)，无论最好、最坏还是平均情况都是如此。这个复杂度由两部分组成：

1. 建堆：使用向下调整的 Floyd 方法，只需 O(n) 时间。
      从最后一个非叶子节点开始调整，每个节点的调整代价与其高度成正比，整体加起来是线性复杂度。
2. 排序：需要执行 n 次 删除堆顶操作。
      每次删除后都要从根向下调整，调整代价为 O(log n)，所以这部分的复杂度是 O(n log n)。

总时间复杂度 = O(n) + O(n log n) = O(n log n)。
空间复杂度为 O(1)，是原地排序，但不稳定。

另外，如果你的建堆方式是逐个插入（向上调整），建堆本身就会是 O(n log n)，但总复杂度依然是 O(n log n)，不过实际效率不如 Floyd 方法。

void HeapSort(HPDataType* a, int n)
{
//降序 建小堆
//升序 建大堆
//for (int i = 1; i < n; i++)
//{
//AdjustUp(a, i);
//}

for (int i = (n-1-1)/2; i >=0; i–)
{
AdjustDown(a, n, i);
}

int end = n – 1;
while (end>0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
–end;
}
}

topk问题

在现实生活中，经常会有在一堆数据中找最小或最大的前K个，比如找出全球最富有的前十个人，有时这些数据很少，用堆排序即可实现，但是当数据量很大，占据的内存很多时，该怎么解决？

假设求100000个数字中最大的前K个

1.建一个只有K个数的小堆

2.将剩下的n-k个数与堆顶比较，如果大于堆顶，则将两个数交换，再向下调整

void CreatNode()
{
int n = 100000;
srand((unsigned)time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; i++)
{
int x = (rand() + i) % 10000000000;
fprintf(fin, "%d\\n", x);
}
fclose(fin);
}

void test_3()
{
int k = 0;
printf("请输入要找的前？个数");
scanf_s("%d", &k);
int* kmaxheap = (int*)malloc(sizeof(int) * k);
if (kmaxheap == NULL)
{
perror("malloc fail");
return;
}

const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}

//读取文件中前k个树
for (int i = 0; i < k; i++)
{
fscanf_s(fout, "%d", &kmaxheap[i]);
}

//建堆
for (int i = (k – 1 – 1) / 2; i >= 0; i–)
{
AdjustDown(kmaxheap, k, i);
}

//遍历剩下的n-k个数
int x = 0;
while (fscanf_s(fout, "%d", &x) > 0)
{
if (x > kmaxheap[0])
{
kmaxheap[0] = x;
AdjustDown(kmaxheap, k, 0);
}
}

printf("最大的前%d个数：", k);
for (int i = 0; i < k; i++)
{
printf("%d ", kmaxheap[i]);
}
printf("\\n");
}
int main()
{
//test_1();
//test_2();
//CreatNode();
test_3();

return 0;
}

该算法的时间复杂度为O(n) = (N-K)logN