树的存储表示
1、使用指针数组
弊端:只有根节点的度是6,其他结点小于6,就会浪费定义的指针
2、使用顺序表
优势:每个结点有几个孩子就插入几个孩子,不够就再扩容
C不太好表示
C++有一个库叫vector就是顺序表,vector<struct TreeNode*>subs
3、左孩子右兄弟表示法
windows文件目录就是一个森林
二叉树
二叉树:
是一个特殊的树,结点的度最大为2
存储:
1、顺序存储
2、链式存储
完全二叉树:
前h-1层是满的,最后一层可以不满,但是从左到右必须连续存在
非完全二叉树就不适合数组结构存储,只适合链式存储
满二叉树:
结点的度都为2
二叉搜索树:
左子树小于右子树,不是完全二叉树
查找数字是只需要和根结点比大小,最多查找高度次
AVL树:
红黑树:
堆
堆逻辑结构是完全二叉树,存储结构是数组
堆不一定有序,孩子之间没有大小关系
以上都不是堆
数据结构的堆:
完全二叉树,是一个数据结构
操作系统的堆:
内存区域的划分
是不同学科里的同名名称
意义:
1、堆排序
时间复杂度为O(N*logN),根是最大的,只需要调整高度次顺序
1000h=10(N)
100wh=20
100亿h=30
2、top k问题
N个数里面找最大前k个(N远大于k)
实践
思路:
push:
向上调整算法时间复杂度是高度次,也就是O(logN)。和向下调整算法一样
pop:
不能挪动删除
首尾交换,尾删掉原来的头结点,再对上面那个小三角使用向下调整算法,也就是选取根节点的最小子节点进行算法运算
将受到影响的最小子节点所在的树一直更新,循环使用算法运算直到到叶子结点
那么怎么判断到达叶子结点,先照旧算出子节点的下标值,再和size比较
这样子树都没有被破坏,依旧是小堆
Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;typedef struct Heap {HPDataType* a;int size;int capacity;
}HP;void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
//规定删除根结点
void HPPop(HP* php);
HPDataType HpTop(HP* php);
size_t HPSize(HP* php);
bool HPEmpty(HP* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"void HPInit(HP* php) {assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}void HPDestroy(HP* php) {assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2) {//只交换内部的值HPDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child) {//child和parent都是下标int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;//往上走}elsebreak;}
}void HPPush(HP* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL) {perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}//插入到最后php->a[php->size] = x;php->size++;//调整顺序AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a, int size, int parent) {int child = parent * 2 + 1;//child为小的孩子while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {//交换成小的孩子时,要保证父节点有右孩子++child;}if (a[parent] > a[child]) {Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}void HPPop(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 HpTop(HP* php) {assert(php);assert(php->size > 0);return php->a[0];
}size_t HPSize(HP* php) {assert(php);return php->size;
}bool HPEmpty(HP* php) {assert(php);return php->size == 0;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"int main() {int a[] = { 4,6,2,1,5,8,2,9 };HP hp;HPInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {HPPush(&hp, a[i]);}获取最小的前k个//int k = 3;//while (k--) {// printf("%d\n", HpTop(&hp));// HPPop(&hp);//}while (!HPEmpty(&hp)) {printf("%d ", HpTop(&hp));HPPop(&hp);}printf("\n");return 0;
}
Top k问题
N个数里面找最大前k个(N远大于k)
思路一:
N个数插入到大堆里面,Pop k次
时间复杂度:N*logN +k*logN -> O(N*logN)
内存不够,就会放入磁盘的文件里
思路二:
找大的,建小堆
大的数就沉在堆底,挤出去小的
时间复杂度:O(N*logk)