[数据结构]二叉树--堆-创新互联

创新互联公司服务项目包括浏阳网站建设、浏阳网站制作、浏阳网页制作以及浏阳网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，浏阳网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到浏阳省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！堆

• • 什么是堆
  • 堆的实现
  • • • 类的定义
      • 构造函数
      • 析构函数
      • push
      • 向上调整
      • 判断堆是否为空
      • 返回堆中有效数据个数
      • 返回堆顶的数据
      • pop数据,删除堆顶的数据
      • 向下调整
  • 堆的应用
  • • • TopK问题
      • 堆排序
      • • 1.第一种建堆方式-->向上调整
        • 2.第二种建堆方式--->向下调整
        • 排序
  • 总结

什么是堆

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

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

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

堆的性质:

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

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

大堆

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

堆的实现

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

类的定义

templateclass Heap
{public:
	Heap();
	void push(T val);
	void pop();
	T Top();
	bool empty();
	size_t size();
	~Heap();

private:
	T* _data;
	int _top;//指向最后一个数据的下一个位置
	int _capacity;
};

构造函数

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

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

析构函数

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

~Heap()
{free(_data);
	_top = _capactiy = 0;
}

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

向上调整

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

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

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

判断堆是否为空

这个相对比较简单

bool empty()
{//如果top等于0为空
		return _top == 0;
}

返回堆中有效数据个数

size_t size()
{return _top;
}

返回堆顶的数据

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

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

pop数据,删除堆顶的数据

我们来分析一下

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

		--_top;
		//向下调整
		AdjustDown(_data, n, 0);
}

向下调整

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

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

堆的应用 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);
}

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

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

排序

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

利用堆的特性, 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;
	}
}

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

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

总结

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：[数据结构]二叉树--堆-创新互联
文章源于：http://cqcxhl.com/article/ceedce.html