C++实现最大堆

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++实现最大堆，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1504字，纯文字阅读大概需要3分钟。

内容图文

C++实现最大堆

前言：

堆是一种数据结构，有着广泛的应用。
例如：
优先队列
堆排序

**误解：**很多人都误解堆是一颗二叉树，但是我们只是说堆形如一颗二叉树（平衡二叉树），但堆并没有左右子节点，而是一个数组

最大堆的定义：

任一结点的关键码均大于等于它的左右孩子的关键码，其中堆顶的元素最大。（任一路径中的元素升序排列）

计算公式：

当我们已知父节点时：计算孩子节点的位置
左孩子节点 = 2父节点+1
右孩子节点 = 2父节点+2
**已知孩子节点：**计算父节位置时
父节点 = （孩子节点-1）/ 2

最大堆的实现：

#pragma once
#include<iostream>
#include<vector>
template<class T>
class maximumHeap
{
public:

	maximumHeap()
	{

	}

	maximumHeap(const T* res)
	{
		heap.push_back(*res);
	}

	void createHeap(const T* root)
	{
		heap.push_back(*root);

		int index = heap.size() - 1;

		int parent = (index - 1) / 2;

		while (parent >= 0)
		{
			if (heap[index] > heap[parent])
			{
				T tmp = heap[index];

				heap[index] = heap[parent];

				heap[parent] = tmp;

				index = parent;

				parent = (parent - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	T* getHeapTop()
	{
		if (emptyHeap())
		{
			return NULL;
		}
		return heap.begin();
	}

	void travelHeap()
	{
		for (auto i : heap)
		{
			std::cout << "堆的值为：" << i << endl;
		}
	}

	size_t heapLength()
	{
		return heap.size();
	}

	//删除堆顶元素
	void popHeap()
	{
		if (emptyHeap())
		{
			return;
		}

		int heapLength = heap.size() - 1;

		heap[0] = heap[heapLength];

		heap.pop_back();

		int parent = 0;

		int son = 2 * parent + 1;

		while (son < heapLength - 1)
		{
			if (heap[parent] < heap[son])
			{
				swap(heap[parent], heap[son]);

				parent = son;

				son = son * 2 + 1;
			}
		}
	}

	bool emptyHeap()
	{
		return heap.empty();
	}
private:
	vector<T> heap;
};

最小堆只是改变一下比较条件即可，欢迎点赞收藏

内容总结

以上是互联网集市为您收集整理的C++实现最大堆全部内容，希望文章能够帮你解决C++实现最大堆所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端