【数据结构】二叉查找树和二叉堆_二叉堆查找

前面我们简单介绍了一下二叉树的定义和特点(34条消息) 【数据结构】初识二叉树_薄荷冰ovo的博客-CSDN博客

下面让我们从二叉树的应用讲起。

1.二叉树的查找

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树

 这样在从二叉树中查找一个数时，时间复杂度可以达到

2.二叉堆

比大小一直是编程种很重要的一环，但有时候我们并不需要知道所有的排名，而是只要一小部分。及TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。这时我们通常采用堆(一种二叉树)来解决这种问题。 需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.1堆的概念及其结构

如果有一个关键码的集合K = { ，,…， }，把它的所有元素按完全二叉树的顺序存储方式存储

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树

根据大根和小根我们将堆分为大堆小堆

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堆的插入、删除、构建操 作的时间复杂度

3.二叉堆的应用

3.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[end], &a[0]);
		AdjustDown(a, end, 0);
 
		--end;
	}
}

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);
}