数据结构 — 堆基本概念以及基本操作

野性酷女 2022-06-15 00:55 312阅读 0赞

# 堆的基本概念和基本操作 #

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。 堆是一种特殊的树形数据结构，每个结点都有一个值。

二叉堆满足的特征:

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为**最大堆**。

当父结点的键值总是小于或等于任何一个子节点的键值时为**最小堆**。

![20170519084834737][]

这个堆是不是很有趣呢~ 现在开始我们开始了解它，首先我们应该知道堆是如何创建的，这里我有首先了解一个概念:向下调整

举个例子这里我建的是一个大堆，我需要一个函数来交换子节点大于父节点的节点们，现在我附上代码:

（注意今天的方法都是用数组模仿堆的实现的）

# 向下调整： #

template<class T>
    	struct Less
    	{
    		bool operator()(const T& l, const T& r)const
    		{
    			return l < r;
    		}
    	};
    	template<class T>
    	struct Greator
    	{
    		bool operator()(const T& l, const T& r)const
    		{
    			return l > r;
    		}
    	};
    	void _AdjustDown(int parent)
    	{
    		Compare ptr;
    		int child = parent * 2 + 1;
    		while (child < _a.size())
    		{
    			if (child + 1 < _a.size() && ptr(_a[child + 1], _a[child]))
    			{
    				++child;
    			}
    			if (ptr(_a[child] , _a[parent]))
    			{
    				swap(_a[parent], _a[child]);
    				parent = child;
    				child = parent * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}

这里我用到仿函数，对代码的复用性提升，小堆的向下调整和大堆神似(99%相似),所以我用到仿函数对他们进行复用。我们看看调用过程：

![20170519090506665][]

现在我们来看向下调整的代码，它的核心思想就是如果如果孩子节点里面较大的那个结点的值大于父节点那么就让他们交换，然后

顺着一条路径往下走，显然调用一次不足以创建一个堆，所以建堆是一个过程.

![20170519091041034][]

# 建堆: #

现在我们来了解如何建堆，因为堆数据结构是一种数组对象，这里我是用一个数组模仿堆的创建，看代码：

Heap(T* a, size_t n)
    	{
    		_a.reserve(n);
    		for (size_t i = 0; i < n; ++i)
    		{
    			_a.push_back(a[i]);
    		}
    		for (int i = (_a.size() - 2) / 2; i>=0; --i)
    		{
    			_AdjustDown(i);
    		}
    	}

这里的\_a是一个vector对象，我们看到用它自带的push把数据压入\_a。

![20170519091600337][]

#     #

# 堆的插入: #

堆的插入这里有几点需要注意：

1.首先堆其实也是一个数组管理，这里的插入只能从尾部插入

2.当堆在尾部插入的之后，如果需要(大堆情况下，插入数据大于父节点)，这时候我们就需要一个函数向上调整.

3.使用这个函数，只是一条路径上的，其他地方还是原来的样子，所以不需要向下调整.

好的附上代码:

//向上调整
    	void _AdjustUp(int child)
    	{
    		Compare fun;
    		int parent = (child - 1) >> 1;
    		while (child > 0)
    		{
    			if (fun(_a[child], _a[parent]))
    			{
    				swap(_a[child], _a[parent]);
    				child = parent;
    				parent = (child - 1) >> 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    	//插入数据
    	void Push(const T& x)
    	{
    		_a.push_back(x);
    		_AdjustUp(_a.size() - 1);
    	}

这里的向上调整也使用到了仿函数实现代码复用，其实我们也可以看出来逻辑很简单.

![20170519092628597][]

# 堆的删除: #

这里堆得删除也有几个注意的点：

1.头删的代价太大，我们灵巧一点，把头和尾先换掉，然后pop掉尾就行了.

2.现在当我删掉之后(假设为大堆，现在最小的堆顶，所以我们需要向下调）.

3.每次的向下调整都从堆顶开始.

实现代码:

void Pop()
    {
    	assert(!_a.empty());
    	swap(_a[0], _a[_a.size() - 1]);
    	_a.pop_back();
    	_AdjustDown(0);
    }

现在堆的基本操作也就完了，其实也不难我们学习是它的思想.

现在我们来看看堆的一个实际的应用:

举个例子我现在是一家游戏公司的老板，我们公司有一个很火爆的游戏，现在我要选出国服里面基本最高的前50个玩家，给他们配

送限量道具，前提这个游戏很火爆玩家很多. 现在要求写一个算法来求出这50个人.如果你告诉我，创建一个数组把所以人的数据导

进去，然后再用冒 泡排序，那我真的没办法说什么了，注意这里的游戏火爆，玩家 一定非常的多，你觉得要开一个多大空间的数

组？ 当人数足够大的时候，内存甚至放 不下. 其实在这里用我们的堆可以完美的解决，这也就是堆中的TOPK的问题，现在我们来想

想如何解决这个问题.

TOPK问题的注意要点:

1.这里你找的是最大的前K个玩家，所以我们需要建一个容量为K的小堆.(为什么建小堆？ 如果建大堆，最后你拿到的只有那个最大的数据)

2.现在小堆我建好了，我们只需要遍历这些数据，当遍历到的数据大于堆顶的数据(堆里最小的),那么我们让堆顶数据等于遍历到的

数据

3.每次堆顶数据改变，我们都得进行一次向下调整.

实现代码:

void _AdjustDown(int* heap, int k, size_t parent)
    {
    	size_t child = parent * 2 + 1;
    	while (child < k)
    	{
    		if (child + 1 < k && (heap[child + 1] < heap[child]))
    		{
    			++child;
    		}
    		if (heap[parent] > heap[child])
    		{
    			swap(heap[parent], heap[child]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void Topk(int* a, int k, int n)
    {
    	assert(k < n);
    	int* heap = new int[k];
    	for (size_t i = 0; i < k; ++i)
    	{
    		heap[i] = a[i];
    	}
    	//topk建小堆 
    	for (int i = (k - 2) / 2; i>0; --i)
    	{
    		_AdjustDown(heap,k,i);
    	}
    	//然后从头遍历n或者传进来的数组。
    	for (int i = 0; i < n; i++)
    	{
    		if (a[i]>heap[0])
    		{
    			heap[0] = i;
    			_AdjustDown(heap, k, 0);
    		}
    	}
    	cout <<n<<"以内最大的" << k << "个数字分别为:" << " ";
    	for (int i = 0; i < k; i++)
    	{
    		cout << heap[i] << " ";
    	}
    	cout << endl;
    	delete[] heap;
    }

![20170519095039373][]

所有实现代码:

#include<iostream>
    #include<Windows.h>
    #include<vector>
    #include<assert.h>
    #include<memory>
    using namespace std;
    
    
    
    
    //**********************************************************************************************//
    //*******************************创建一个堆(大小堆)*********************************************//
    
    
    template<class T>
    struct Less
    {
    	bool operator()(const T& l, const T& r)const
    	{
    		return l < r;
    	}
    };
    template<class T>
    struct Greator
    {
    	bool operator()(const T& l, const T& r)const
    	{
    		return l > r;
    	}
    };
    
    
    template<class T,class Compare>
    class Heap
    {
    public:
    	Heap()
    	{}
    	Heap(T* a, size_t n)
    	{
    		_a.reserve(n);
    		for (size_t i = 0; i < n; ++i)
    		{
    			_a.push_back(a[i]);
    		}
    		for (int i = (_a.size() - 2) / 2; i>=0; --i)
    		{
    			_AdjustDown(i);
    		}
    	}
    
    	void Push(const T& x)
    	{
    		_a.push_back(x);
    		_AdjustUp(_a.size() - 1);
    	}
    
    	void Pop()
    	{
    		assert(!_a.empty());
    		swap(_a[0], _a[_a.size() - 1]);
    		_a.pop_back();
    		_AdjustDown(0);
    	}
    
    	const T& Top()  const
    	{
    		return _a[0];
    	}
    
    	
    
    	
    
    protected:
    
    
    	void _AdjustDown(int parent)
    	{
    		Compare ptr;
    		int child = parent * 2 + 1;
    		while (child < _a.size())
    		{
    			if (child + 1 < _a.size() && ptr(_a[child + 1], _a[child]))
    			{
    				++child;
    			}
    			if (ptr(_a[child] , _a[parent]))
    			{
    				swap(_a[parent], _a[child]);
    				parent = child;
    				child = parent * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}	
    
    	//向上调整
    	void _AdjustUp(int child)
    	{
    		Compare fun;
    		int parent = (child - 1) >> 1;
    		while (child > 0)
    		{
    			if (fun(_a[child], _a[parent]))
    			{
    				swap(_a[child], _a[parent]);
    				child = parent;
    				parent = (child - 1) >> 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    	
    
    
    protected:
    	vector<T>  _a;
    };
    
    
    //**********************************************************************************************//
    //**********************************************************************************************//
    
    
    
    
    
    
    
    
    //**********************************************************************************************//
    //*******************************    top K 问题    *********************************************//
    //top K 问题
    //找出n中最大的k个数
    //传进来的数组
    //这里的参数，如果传的是一个数组的话就是int* a 如果是数字的话直接就是int n，和int k 就够了。
    
    void _AdjustDown(int* heap, int k, size_t parent)
    {
    	size_t child = parent * 2 + 1;
    	while (child < k)
    	{
    		if (child + 1 < k && (heap[child + 1] < heap[child]))
    		{
    			++child;
    		}
    		if (heap[parent] > heap[child])
    		{
    			swap(heap[parent], heap[child]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void Topk(int* a, int k, int n)
    {
    	assert(k < n);
    	int* heap = new int[k];
    	for (size_t i = 0; i < k; ++i)
    	{
    		heap[i] = a[i];
    	}
    	//topk建小堆 
    	for (int i = (k - 2) / 2; i>0; --i)
    	{
    		_AdjustDown(heap,k,i);
    	}
    	//然后从头遍历n或者传进来的数组。
    	for (int i = 0; i < n; i++)
    	{
    		if (a[i]>heap[0])
    		{
    			heap[0] = i;
    			_AdjustDown(heap, k, 0);
    		}
    	}
    	cout <<n<<"以内最大的" << k << "个数字分别为:" << " ";
    	for (int i = 0; i < k; i++)
    	{
    		cout << heap[i] << " ";
    	}
    	cout << endl;
    	delete[] heap;
    }
    
    //**********************************************************************************************//
    //**********************************************************************************************//

[20170519084834737]: /images/20220615/4619da006fef43bdab0a8631aeb62dc4.png
[20170519090506665]: /images/20220615/631d9ab8295c44a788459d2444e12445.png
[20170519091041034]: /images/20220615/b392967d114642a995b6f806d98b14f3.png
[20170519091600337]: /images/20220615/e49ef8b0ee0b4fc3990ef43c9fee545d.png
[20170519092628597]: /images/20220615/59f9c11779b344cdb9fa58b726d5572f.png
[20170519095039373]: /images/20220615/ae91ba14afa2486ebe33237ea4120d9c.png