数据结构与算法——堆的原理和实现

目录

一、堆的原理

二、堆的实现

1.堆的定义

2.堆的初始化

3.向上调整算法

4.向上调整算法代码实现

5.堆的插入

6.向下调整算法

6.堆的删除

7.堆的大小

8.判断堆是否为空

总结

---

一、堆的原理

堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

“堆”的各地常用别名
中国大陆	堆
港台	堆积

堆始于JWJ Williams（英语：JWJ Williams）在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

堆是一种特殊的二叉树，完全二叉树，它是非线性结构，物理结构与逻辑结构不同

堆的底层是数组，而我们想象出来操控的却是一棵树

逻辑结构

物理结构：

 

 

堆分为大根堆和小根堆

大根堆：所有的父节点都大于等于子节点

小根堆：所有的父节点都小于等于子节点

堆分为左孩子，右孩子

右孩子的下标全是偶数

左孩子的下标全是奇数

二、堆的实现

1.堆的定义

我们的堆是用数组来实现，所以需要容量和数组当前储存元素的个数，和一个指针

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

2.堆的初始化

初始化与顺序表类似

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

3.向上调整算法

我们必须要先说明向上调整算法。才能解决堆元素的插入

堆的插入，没有说明要在堆的哪里插入

我们也并不关心它要插入到哪里

因为作为堆，它有堆的特性，导致它的所有的父节点都要大于等于或者小于等于它的孩子

但是两个孩子之间的大小关系并没有明确的规定

因此有了一种思路，利用数组尾插的时间复杂度是O（1）的特性，我们将元素插入到数组的尾

然后向上调整数组，直至将数组调整成一个堆

但是向上调整算法有两种调整方向

一种是调成小堆，一种是调整成大堆

我们以调成小堆为例来说明

我们的堆有一个下标规律

知道parent的下标，我们就可以求出孩子的下标

leftchild=parent*2+1；

rightchild=parent*2+2；

而知道孩子的下标，父亲的下标为

parent=（child-1）/2；

这个是不用区分左右孩子的，因为根据语言特性，两个int型变量相除还是int

直接就忽略了小数部分，导致奇数和偶数除2是相等

这个规律是前人总结出来的，我们直接拿来用就可以了

调成小堆就是parent的值小于等于child

我们直接处理大于的情况就OK了

一直处理到child到堆的顶就结束了

我们要使用向上或向下调整算法，一定要保证，堆的左子树和右子树都是堆

4.向上调整算法代码实现

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = 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;
		}
	}
}

向下调整算法的时间复杂度是O(logN)

5.堆的插入

我们前面引入了向下调整算法

我们的插入只要在数组尾插入数据，然后调用adjustDown函数就能够完成

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
 
	if (php->capacity == php->size)
	{
		int newCapacity = php->capacity == 0 ? 3 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp== NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity=newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
 
	Adjustup(php->a, php->size - 1);
}

6.向下调整算法

向下调整算法与向上调整类似

不过传的元素是不同的

我们是从数组的第一个位置开始向下调整，然后有一个调整结束位置

我们对这个函数设计与向上调整算法不同

因为这个函数的用处不只是从堆的头调整到尾

这个函数要可以调整任意位置的元素，在后面的堆排序有大用处

同时我们要选出左右孩子中较小的那个

因为我们还是要调整成为小堆

有人会问，为什么要找出左右孩子中较小的，找最大的不可以吗？

我们还是以上面的例子为例

如果我们找出较大的，然后交换，会发生什么呢？

 

我们发现我们还需要调整第一层的元素，我们如果调整最小的就可以避免调整两次

 

然后我们继续调整第二层就好了 

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

6.堆的删除

堆的删除就需要用上我们的向下调整算法

我们要删除堆顶的元素，不可能采取向前挪动元素的方式

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;
		}
	}
}
 
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
 
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	Adjustdown(php->a, php->size, 0);
 
}

(1).这种算法首先时间复杂度是O(N)

(2).向前挪动数据会打乱堆的元素顺序，向前挪动之后我们无法保证这个数组还是堆，如果不是堆，我们还需要将其调整为堆，这样来说时间复杂度就过高了，甚至还不如采取冒泡排序

7.堆的大小

堆的size不就是堆的大小吗，直接返回它就可以了

int HeapSize(Heap* php)
{
	assert(php);
 
	return php->size;
}

8.判断堆是否为空

根据我们堆的定义，size为0就是空

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

三、堆排序

堆排序的时间复杂度是O(N*logN)，这是一种比较高效的排序算法，并且我们在实现堆排序时并不需要，写上述的代码，只需写出向上调整算法和向下调整算法

我们以升序排列为例

我们要排升序需要建大堆

这与我们的常识不符

小堆的堆顶是堆中的最小值，我们拿到了最小值之后，剩余的元素不符合堆的定义

还是要建堆，每次都建堆选数据整体的时间复杂度是O(N^2）不是不可以，而是效率太低，没有用到堆的优势，这样还不如使用冒泡排序，冒泡排序的时间复杂度也是O(N^2)

所以要建大堆

我们建好大堆了，拿到最大的元素，将最大元素与堆的最后元素交换，交换后，这个堆的左子树和右子树都是堆，可以继续调整

选择好建何种堆之后，我们有两种建堆方式，一种是向上调整法，另一种是向下调整法

我们选择向下调整调整法建堆

我们必须明确堆必须左右子树都是堆，我们可以先将左子树调整成堆，然后将右子树调整成堆

类似于递归的思想

建好堆，然后将最大值与堆的最后一个元素交换，然后向下调整时，不需要调整了，这时我们在向下调整函数传参的设计的优势显示出来了

我们向下调整的元素个数越来越少，直到调到堆的顶

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
 
//升序
void adjustDown(int* a, int n, int parent)
{
	assert(a);
 
	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;
		}
	}
}
 
void HeapSort(int*a,int 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]);
		adjustDown(a, end, 0);
		end--;
	}
	
}
void testHeapSort()
{
	int a[] = { 16,72,31,23,94,53 };
	int n = sizeof(a) / sizeof(a[0]);
 
	HeapSort(a, n);
 
 
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
 
int main()
{
	testHeapSort();
 
	return 0;
}

 

---

总结

以上就是今天要讲的内容，topk问题下一篇文章讲解。