发布时间：2023-02-05 08:00
目录
一 树的概念与结构
二 二叉树的概念与结构
1 二叉树的概念：
2 二叉树的性质：
3 树的存储结构
三 堆
1 堆的基本性质
2 向下调整算法
3 建堆
4 堆排序 O(N*logN）
5 堆的实现（封装）
6 TOPK问题
1 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。有一个特殊的结点，称为根结点，根节点没有前驱结点，除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。
2 节点的度：一个节点含有的子树的个数称为该节点的度。
3 叶节点或终端节点：度为0的节点称为叶节点。
4 非终端节点或分支节点：度不为0的节点。
5 兄弟节点：具有相同父节点的节点互称为兄弟节点。
6 树的度：一棵树中，最大的节点的度称为树的度。
7 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
1.1 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
1.2 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。 二叉树的子树有左右之分，其子树的次序不能颠倒。
2.1 特点：左子树与右子树恰好是小堆时可以使用向下调整算法建立小堆。
2.2 向下调整算法：①选出左右孩子中小的那个树。②小的孩子与父亲比较，a、如果小的孩子比父亲小，则跟父亲交换，并且把原来孩子的位置当成父亲，继续向下调整，直到走到叶子节点。b、如果小的孩子比父亲大，则不需要继续调整，整个树已经是小堆。
2.3 代码实现
//交换函数
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//当左右子树都为大堆时，可以使用向下调整算法将整颗树调整为大堆
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//找出左右孩子中大的那一个（建立小堆只需要找到孩子中小的那个）
if (child+1 a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
} 3.1 左右子树不是小堆，随意给一个数组时，从倒数第一个非叶子节点，从后往前，按编号，依次作为子树去向下调整。
3.1.1 建堆代码实现
//建堆（时间复杂度O(N)。）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}4.1 排升序建立大堆，第一个为最大的数，让它与最后一个数交换，将最后一个节点除去，不打乱堆顺序，只需要向下调整即可。
4.1.1 排升序代码实现
//堆排序,排升序要建大堆( 不会打乱堆顺序 )
void HeapSort(int* a, int n)
{
//建堆（时间复杂度O(N)。）
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]);
//选出次大的(顺序没乱，向下调整即可),时间复杂度O(logN)。
AdjustDown(a, end, 0);
end--;
}
}4.2 排降序只需将堆建成小堆即可，每次选出最小的数放到最后。
5.1 Heap.h
#include
#include
#include
#include
#include
typedef int HPDateType;
struct Heap
{
HPDateType* a;
int size;
int capacity;
};
typedef struct Heap HP;
// HP* HeapInit(HPDateType* a, int n);
void Swap(HPDateType* a, HPDateType* b);
void AdjustDown(HPDateType* a, int n, int parent);
void AdjustUp(HPDateType* a, int child);
void HeapInit(HP* php, HPDateType* a, int n);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDateType x);
void HeapPop(HP* php);
HPDateType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);
void HeapPrintf(HP* php); 5.2 Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//交换函数
void Swap(HPDateType* a, HPDateType* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//向下调整算法
void AdjustDown(HPDateType* 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[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//向上调整算法
void AdjustUp(HPDateType* a, int child)
{
int parent = (child-1-1)/2 ;
while (child >0)
{
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//初始化堆
void HeapInit(HP* php, HPDateType* a, int n)
{
assert(php);
php->a = (HPDateType*)malloc(sizeof(HPDateType) * n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDateType) * n);
php->capacity = n;
php->size = n;
//建堆
for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size,i);
}
}
//销毁堆
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
//插入数据
void HeapPush(HP* php, HPDateType x)
{
assert(php);
//满了需要扩容
if (php->size == php->capacity)
{
HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * php->capacity * 2);
if (tmp == NULL)
{
printf("relloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
//向上调整算法
AdjustUp(php->a,php->size-1);
}
//删除堆顶数据
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);
}
HPDateType HeapTop(HP* php)
{
assert(php);
assert(php->size>0);
return php->a[0];
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size==0;
}
//打印堆
void HeapPrintf(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n\n");
int num = 0;
int leveSize = 1;
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
++num;
if (num == leveSize)
{
printf("\n");
num = 0;
leveSize *= 2;
}
}
printf("\n\n");
}
//
5.3 main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
int main()
{
int a[] = {1,58,45,79,16,25,48,33,15,88};
int n = sizeof(a) / sizeof(a[0]);
HP hp;
HeapInit(&hp, a, n);
HeapPrintf(&hp);
//插入
HeapPush(&hp, 99);
HeapPrintf(&hp);
HeapPush(&hp, 8);
HeapPrintf(&hp);
//删除
HeapPop(&hp);
HeapPrintf(&hp);
HeapPop(&hp);
HeapPrintf(&hp);
HeapDestroy(&hp);
return 0;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
if(k==0)
{
* returnSize=0;
return NULL;
}
int* array=(int *)malloc(sizeof(int)*k);
//前K个数建立大堆
for(int i=0;i=0;j--)
{
AdjustDown(array,k,j);
}
//剩下的N-K个数，只要比堆顶的数据小，就替换堆顶，并向下调整。
for(int i=k;iarr[i])
{
array[0]=arr[i];
AdjustDown(array,k,0);
}
}
*returnSize=k;
return array;
}