[数据结构] 二叉树--堆

什么是堆

注意大家在学习编程的过程中, 肯定听说过内存中的堆和栈以及静态区这种的, 这些是属于操作系统虚拟进程地址空间中的,
我们要说的堆和这个并不是一回事,堆是二叉树的一种, 是数据结构的一种,我们来看看吧

普通的二叉树不使用数组来存储,只有堆用数组来存储,
所以说堆的逻辑结构是二叉树, 物理结构是数组

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

堆的性质:

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

小堆: 子节点都比不小于父节点

大堆

那我们尝试用数组来实现这种数据结构

堆的实现

那我们来分析一下堆这个类中需要哪些成员,

类的定义

template <class T>
class Heap
{
public:
	Heap();
	void push(T val);
	void pop();
	T Top();
	bool empty();
	size_t size();
	~Heap();

private:
	T* _data;
	int _top;//指向最后一个数据的下一个位置
	int _capacity;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

构造函数

默认构造就是把成员都初始化一下,我这里没有开默认空间, 大家可以选择开

Heap()
:_data(nullptr)
, _top(0)
, _capacity(0)
{}

1
2
3
4
5
6
7

析构函数

析构函数进行资源清理,所以要把申请的空间都释放掉

~Heap()
{
	free(_data);
	_top = _capactiy = 0;
}
1
2
3
4
5
6

push

push就是插入一个数据,堆这里的插入和其他数据结构不同, 堆插入任何一个数据都要保证堆的特性, 不可以本来是堆,最后不是堆, 我们来分析一下,我们这里都以建大堆为例子

插入的代码比较简单,关键是向上调整,插入唯一需要注意的就是扩容的问题

void push(T val)
{
	//如果容量 == 个数
	if (_capacity == _top)
	{
		//扩容 -- >2倍扩容
		int newCapacity = _capacity == 0 ? 4 : _capacity * 2;
		T* ptr = (T*)realloc(_data, sizeof(T) * newCapacity);
		if (nullptr == ptr)
		{
			perror("realloc fail");
			exit(-1);
		}
		_capacity = newCapacity;
		_data = ptr;
	}
	
	//扩容完毕
	_data[_top] = val;
	//++ 长度
	++_top;
	//向上调整
	AdjustUp(_data, _top - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

向上调整

为了保证堆的特性而向上调整,

那我们来分析一下这个向上调整该如何实现

void AdjustUp(T* data, int child)
{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			//这里是以大堆为例,如果孩子大于父亲, 那么就调整
			if (data[child] > data[parent])
			{
				swap(data[child], data[parent]);
				//迭代
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

判断堆是否为空

这个相对比较简单

bool empty()
{
		//如果top等于0为空
		return _top == 0;
}
1
2
3
4
5

返回堆中有效数据个数

size_t size()
{
	return _top;
}
1
2
3
4

返回堆顶的数据

首先要判断堆是否为空, 如果堆不为空, 还取个啥啊

T Top()
{
	assert(!empty());	
	return _data[_top - 1];
}
1
2
3
4
5

pop数据,删除堆顶的数据

我们来分析一下

void pop()
{
		assert(!empty());
		//交换堆顶的数据和最后一个数据
		swap(_data[0], _data[_top - 1]);

		--_top;
		//向下调整
		AdjustDown(_data, n, 0);
}
1
2
3
4
5
6
7
8
9
10

向下调整

核心思想就是如果大孩子大于根节点, 就交换,直到最后欧一层

void AdjustDown(T* data, int n, int parent)
	{
		//先给出左孩子
		int child = parent * 2 + 1;

		while (child < n)
		{
			//如果右孩子存在,并且比左孩子大
			if (child + 1 < n && data[child + 1] > data[child])
				child++;
			if (data[child] > data[parent])
			{
				swap(data[child], data[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

堆的应用

TopK问题

关于TopK问题,用堆解决是非常合适的问题,我之前写过一篇 TopK问题详解

堆排序

堆排序是一种非常厉害的排序, 核心思想就利用了堆这种数据结构,我们来看看吧,我们距离

如果排升序的话,我们建小堆还是大堆呢??我们来分析一下

那我们该如何建堆呢?

1.第一种建堆方式–>向上调整

插入建堆

int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);

for (int i = 1; i < len; ++i)
{
	AdjustUp(arr, i);
}
1
2
3
4
5
6
7

2.第二种建堆方式—>向下调整

向下调整建堆就是二叉树的典型分治思想,我们来分析一下

int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);

	//建堆 最后一个节点的下标是len-1  ,所以它的父亲下标是(len-2)/2
for (int i = (len - 1 - 1) / 2; i >= 0; --i)
{
	AdjustDown(arr, len, i);
}
1
2
3
4
5
6
7
8

所以更推荐使用向下调整的方式来建堆,因为复杂度比较低

排序

建好堆了以后就相对比较简单了,

利用堆的特性, pop的思想,把最大的放到最后面, 然后调整前面的

void HeapSort(int* arr, int len)
{
	//建堆
	for (int i = (len - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, len, i);
	}
	int end = len - 1;
	while (end > 0)
	{
		swap(arr[0], arr[end]);
		AdjustDown(arr, end, 0);
		--end;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

建堆的复杂度O(N) , 调整的复杂度O(N* logN)

所以堆排序的复杂度就是O(N*logN)

总结

堆还是非常常用的,一定要利用堆的特性, 后面的优先级队列还会涉及到,
感谢收看