普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 堆的概念及实现

如果有一个关键码的集合 K = {k0，k1，k2，... ，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2*i+1 且 Ki <= K2*i+2（Ki >= K2*i+1 且 Ki >= K2*i+2），i = 0，1，2...，则称为小堆(大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

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

3. 堆的实现

3.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

3.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

3.3 建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

因此： 建堆的时间复杂度为 O(N) 。

3.4 堆的插入

先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。

3.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

4. 堆的代码实现（小堆）

在了解堆的基本实现逻辑后，就可以试着实现整个代码了

堆的结构定义


typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

堆的初始化


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

堆的销毁


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

堆的打印


void HeapPrint(HP* php)
{
	assert(php);
 
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
 
	printf("\n");
}

交换两元素值的函数


void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

向上调整算法


void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
 
	while (child < size)
	{
		if (child + 1 < size && 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 HeapPush(HP* php, HPDataType x)
{
	assert(php);
 
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
 
		php->a = tmp;
		php->capacity = newCapacity;
	}
 
	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);
}

堆的判空


bool HeapEmpty(HP* php)
{
	assert(php);
 
	return php->size == 0;
}

求堆的数据个数


size_t HeapSize(HP* php)
{
	assert(php);
 
	return php->size;
}

取堆顶的数据


HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}

5. 堆的应用

在我们实现堆后，堆可以用来解决一些实际问题

堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆
降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

堆排序代码实现


void HeapSort(int* a, int n)
{
	// 向上调整建堆 O(N*logN)
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, n);
	}*/
 
	// 向下调整建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	int j = n;
	while (--j)
	{
		Swap(&a[0], &a[j]);
		AdjustDown(a, j, 0);
	}
}

TOP-K问题

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。

最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前 K 个元素来建堆

前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

TOP-K问题代码实现


void PrintTopK(int* a, int n, int k) 
{
 
	// 1. 建堆--用a中前k个元素建堆
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	assert(kminHeap);
	for (int i = 0; i < k; ++i)
	{
		kminHeap[i] = a[i];
	}
	//建小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(a, k, j);
	}
 
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);
		}
	}
	for (int j = 0; j< k; ++j)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}
 
void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int)*n);
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2335] = 1000000 + 6;
    a[9999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
 
    PrintTopK(int* a, n, 10);
}

6. 堆的使用

我们来建立一个test函数来测试一下，这需要调用之前我们所定义的相关函数。


void test()
{
	HP hp;
	HeapInit(&hp);
	
	HeapPush(&hp, 1);
	HeapPush(&hp, 5);
	HeapPush(&hp, 0);
	HeapPush(&hp, 8);
	HeapPush(&hp, 3);
	HeapPush(&hp, 9);
	HeapPrint(&hp);
	
 
	HeapPop(&hp);
	HeapPrint(&hp);
 
	HeapDestroy(&hp);
}

7. 完整源码

Heap.h


#pragma once
 
// 小堆
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPrint(HP* php);
 
// 插入x以后，保持他依旧是(大/小)堆
void HeapPush(HP* php, HPDataType x);
 
// 删除堆顶的数据。(最小/最大)
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);

Heap.c


#include "Heap.h"
 
void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
 
void HeapInit(HP* php)
{
	assert(php);
	
	php->a = NULL;
	php->capacity = php->size = 0;
}
 
void HeapDestroy(HP* php)
{
	assert(php);
 
	free(php->a);
	php->a = NULL;
 
	php->capacity = php->size = 0;
}
 
void HeapPrint(HP* php)
{
	assert(php);
 
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
 
	printf("\n");
}
 
void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			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, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
 
	while (child < size)
	{
		if (child + 1 < size && 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);
}
 
bool HeapEmpty(HP* php)
{
	assert(php);
 
	return php->size == 0;
}
 
size_t HeapSize(HP* php)
{
	assert(php);
 
	return php->size;
}
 
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}

test.c


#include "Heap.h"
 
void test()
{
	HP hp;
	HeapInit(&hp);
	
	HeapPush(&hp, 1);
	HeapPush(&hp, 5);
	HeapPush(&hp, 0);
	HeapPush(&hp, 8);
	HeapPush(&hp, 3);
	HeapPush(&hp, 9);
	HeapPrint(&hp);
	
 
	HeapPop(&hp);
	HeapPrint(&hp);
 
	HeapDestroy(&hp);
}
 
void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
 
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
 
	int j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j++] = HeapTop(&hp);
		HeapPop(&hp);
	}
 
	HeapDestroy(&hp);
}
 
int main()
{
	test();
 
	int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
	HeapSort(a, sizeof(a) / sizeof(int));
 
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
 
	return 0;
}

最终实现效果

后续内容，等博主继续学习后分享给大家。请大家继续关注，不断督促，共同进步！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/744406