【数据结构】二叉查找树和二叉堆
【数据结构】二叉查找树和二叉堆
下面让我们从二叉树的应用讲起。
1.二叉树的查找
二叉树的树形结构使它很适合扮演索引的角色。
这里我们介绍一种特殊的二叉树：二叉查找树（binary search tree） 。光看名字就可以知道，这种二叉树的主要作用就是进行查找 操作。
二叉查找树在二叉树的基础上增加了以下几个条件。
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树
下图就是一个标准的二叉查找树
这样在从二叉树中查找一个数时，时间复杂度可以达到
2.二叉堆
比大小一直是编程种很重要的一环，但有时候我们并不需要知道所有的排名，而是只要一小部分。及TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。这时我们通常采用堆(一种二叉树)来解决这种问题。 需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2.1堆的概念及其结构
如果有一个关键码的集合K = {
，
,…，
}，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树
根据大根和小根我们将堆分为大堆小堆
2.2堆的实现
这里我们首先介绍堆的向下调整。所谓向下调整就是从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。简单来说，向下调整就是将根节点和左右孩子节点进行比较若他比左右孩子中的任一数大就进行替换(小堆)，若都小就和左孩子进行替换。与他相似的向上调整就是从最后一个数据与他的父节点进行比较使二叉树最后成为堆，他的前提条件是除该数据外其余数据构成堆。
注意：无论是向上调整还是向下调整，其目的都是形成一个堆，所以除该数据外其余数据构成堆。
//交换位置
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向上调整
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 Adjustdown(HPDataType* a, int n,int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 选出左右孩子中大的那一个
if (child + 1 < n && a[child + 1] > a[child])//确保右孩子不越界
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}2.3堆的创建
如果给定一个数组这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算
法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的 子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
堆的基本操作(插入，删除)
插入就直接将插入的数据放到数组的最后处，然后对他进行向上调整。
删除(特指删除根节点)可以将数组最后的数将根节点覆盖，然后对根节点进行向下调整。
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//扩容
if (hp->_capacity == hp->_size)
{
HPDataType* tmp =(HPDataType*) realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);
if (tmp == NULL)
{
perror("realloc");
return;
}
hp->_capacity *= 2;
hp->_a = tmp;
}
hp->_a[hp->_size] = x;
Adjustup(hp->_a, hp->_size);
hp->_size++;
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
Adjustdown(hp->_a, hp->_size, 0);
}2.4堆的插入、删除、构建操 作的时间复杂度
堆的插入操作是单一节点的“上浮”，堆的删 除操作是单一节点的“下沉”，这两个操作的平均交换次数都是 堆高度的一半，所以时间复杂度是O(logn)。而构建堆的时间复杂度是O(n)推导如下。
3.二叉堆的应用
3.1堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
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[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}3.2TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(const char* file, int k)
{
// 1. 建堆--用a中前k个元素建小堆
int* topk = (int*)malloc(sizeof(int) * k);
assert(topk);
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
// 读出前k个数据建小堆
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &topk[i]);
}
for (int i = (k - 2) / 2; i >= 0; --i)
{
Adjustdown(topk, k, i);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
int val = 0;
int ret = fscanf(fout, "%d", &val);
while (ret != EOF)
{
if (val > topk[0])
{
topk[0] = val;
Adjustdown(topk, k, 0);
}
ret = fscanf(fout, "%d", &val);
}
for (int i = 0; i < k; i++)
{
printf("%d ", topk[i]);
}
printf("\n");
free(topk);
fclose(fout);
}
void CreateNDate()
{
// 造数据
int n = 10000000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 10000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
腾讯云开发者
