【c++】数据结构———堆

Bertha 。 2022-07-15 14:51 176阅读 0赞

堆是一种特殊的数据结构，它通常是一个可以被看做一棵树的数组对象。

What？那它到底是一棵树，还是一个数组呢？答案是数组。这个数组以二叉树的形式来维护。注意：这个二叉树必须是完全二叉树

堆结构的二叉树存储有两种：

**   最大堆**：每个父亲结点的值都大于孩子结点。

**最小堆**：每个父亲结点的值都小于孩子结点。

顾名思义，这种结构就是可以根节点为最大的/最小的结点。不过有一点要注意，堆内的元素并不一定是按数组下标来排序的，很多

初学者会错误的认为最大/最小堆中下标为1的就是第一大/小，下标为2的就是第二大/小。。。。。。

你会问，堆既然是一个数组，那么它如何以二叉树的形式来保存呢？——————答案：下标。

我们先来看一棵二叉树的模型：（这是一棵乱序的完全二叉树）红色数字代表结点的值，黑色数字代表结点的下标。

![20161020085150064][]

以上，我们可以看出，每个根结点的下标  =  （（左/右）孩子结点下标-1）/2，左孩子结点下标 = （根结点\*2）+1，右孩子结点下

标 = （根结点\*2）+ 2。这样我们用数组以下标

方式就可以很好的存储一颗树了（前提是这棵树必须是完全二叉树），我们就会得到一个数组 int a \[\] = \{10,16, 18, 12, 11, 13, 15, 17, 14, 19\};

下面我开始讲如何建立并维护一个堆，以最大堆为例。

假设，我们现在已经有了一个乱序的堆(例上图)，如何让它变成最大堆/最小堆呢？————堆的向下调整，向上调整。

**向下调整**：（调整根结点parent）

我们先要找到数组中存放的最后一个非叶子结点parent（上图中的下标为4值为11的结点）。找出它的左孩子leftchild和右孩rightchild

的最大值MaxChild，与父结点parent进行比较，若MaxChild>parent，则将它们俩的值进行交换。然后令parent的下标 = MaxChild下

标。再重复之前的操作。直到leftChild >= 数组的size。

到这里，我们才完成了一次向下调整，并不足以构成一个最大堆，在向下调整函数外面我们需要加上一个循环，每次向向下调整函数

传入想调整的根结点。（最后一个非叶子结点只是一个循环的‘起点’）

下面看代码：

template<typename T>
    class Heap
    {
    public:
    	//建堆
    	Heap(const T* a, int sz)
    	{
    		_a.resize(sz);
    		for (int i = 0; i < sz; i++)
    		{
    			_a[i] = a[i];
    		}
    		for (int i = (_a.size() - 2) / 2; i >= 0; i--)//外层循环，每次传入根结点下标。（_a.size()-2）/2即为最后一个非叶子结点下标。
    		{
    			AdjustDown(i);
    		}
    	}
    protected:
    	//向下调整
    	void AdjustDown(int root)
    	{
    		int parent = root;
    		size_t child = parent * 2 + 1;
    		while (child < _a.size())//当child>=_a.size()的时候，说明已经越界。
    		{
    			if (child + 1 < _a.size() && _a[child + 1] > _a[child])
    			{
    				child++;
    			}
    			if (_a[child] > _a[parent])
    			{
    				swap(_a[child], _a[parent]);//交换child与parent
    				parent = child;
    				child = parent * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    protected:
    	vector<T> _a;//用Vector来代替一个数组
    };

**向上调整**：（调整孩子结点child）

再来看向上调整，就简单的多了。找到你想调整的结点child，找出它的父亲结点parent，比较两个的大小，若child < parent，不操

作。若child > parent, 则交换两个的值，然后令child的下标 = parent的下标。重复以上操作，直到child的下标 <= 0(说明到达根结点)。

代码：

//向上调整
    void AdjustUp(int root)
    {
    	int child = root;
    	int parent = (child - 1) / 2;
    	Compare com;
    	while (child > 0)
    	{
    		if (!com(_a[child] ,_a[parent]))
    		{
    			swap(_a[child], _a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

依靠上面两个算法，我们就可以建立一个最大堆了，下面我再来讲两个维护堆的算法。

**Push插入**

每次都插到数组最后，然后针对这个结点进行一次向上调整。

//插入
    void Push(const T& x)
    {
    	_a.push_back(x);
    	AdjustUp(_a.size() - 1);
    }

**Pop删除**（删除根结点，即数组第一个元素）

有人可能会想，直接让数组向前挪动一位就行了。错！，如果你这么做，确实达到了删除的效果，但是你破坏了整个堆的结构。

正确的做法是将根结点（第一个元素）与最后一个结点（最后一个元素）进行交换，删除最后一个元素，然后再根结点进行一次向下调整。

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

**堆有什么应用？**

1、堆排序，时间复杂度为O（N\*lgN），最大堆，从小到大排序。最小堆，从大到小排序。

2、优先级队列。

3、大数据筛选，一个文件中包含了1亿个随机数，如何快速找到最大（小）的100W个数字（时间复杂度为O(N\*lgk)）。