【数据结构】中有关堆的讲解

雨点打透心脏的1/2处 2022-06-18 05:21 126阅读 0赞

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是：  
最大堆：每个父节点的都大于孩子节点。  
最小堆：每个父节点的都小于孩子节点。

接下来实现一下堆以及堆中的排序：

#include<iostream>
    using namespace std;
    #include<vector>
    template<typename T>
    class Heap
    {
    public:
    	Heap()
    	{}
    
    	Heap(T arr[], size_t n)
    		:_a(arr,arr+n)
    	{
    		for (int i = (_a.size() - 2) / 2; i >= 0; i--)
    		{
    			_AdjustDowm(i);
    		}
    	}
    
    
    	void Pop()
    	{
    		swap(_a[0], _a[_a.size() - 1]);
    		_a.pop_back();
    		_AdjustDowm(0);
    	}
    
    
    	void Push(const T&x)
    	{
    		_a.push_back(x);
    		_AdjustUp(_a.size() - 1);
    	}
    
    
    protected:
    	vector<T> _a;
    
    protected:
    	//向上调整
    	void _AdjustUp(int i)
    	{
    		int child = i;
    		int parent = (child - 1) / 2;
    
    		while (child >= 0)
    		{
    			if (_a[child] > _a[parent])
    			{
    				swap(_a[child], _a[parent]);
    				child = parent;
    				parent = (parent - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	//向下调整
    	void _AdjustDowm(int root)
    	{
    		int parent = root;
    		int child = 2 * parent + 1;
    
    		while (child < _a.size())
    		{
    			if (child + 1 < _a.size() && _a[child + 1] > _a[child])
    			{
    				child++;
    			}
    
    			if (_a[child]>_a[parent])
    			{
    				swap(_a[child], _a[parent]);
    				parent = child;
    				child = 2 * child + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    };
    
    int main()
    {
    	int arr[10] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    	Heap<int> hp1(arr, sizeof(arr) / sizeof(arr[0]));
    	hp1.Push(11);
    	hp1.Pop();
    	system("pause");
    	return 0;
    }