Heap，堆，大堆和小堆用仿函数实现

#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class T>
class Heap
{
public:
	//vector调用自己的构造函数
	Heap()
	{}
	Heap(T* a, size_t size)
	{
		for (size_t i = 0; i < size; ++i)
			_array.push_back(a[i]);
		//size-1是数组最大下标，再减1除二是父节点下标
		for (int i = (_array.size() - 1 - 1) / 2; i >= 0; --i)
		{
			AdjustDown(i);
		}
	}
	void Push(const T& x)
	{
		_array.push_back(x);
		AdjustUp(_array.size()-1);
	}
	void Pop()
	{
		if (_array.size()>0)
		{
			swap(_array[_array.size() - 1],_array[0]);
			_array.pop_back();
			AdjustDown(0);
		}
	}
protected:
	void AdjustDown(int prtIndex)
	{
		int leftIndex = 0;
		while (prtIndex<_array.size())
		{
			leftIndex = prtIndex * 2 + 1;
			if (leftIndex + 1 < _array.size() && _array[leftIndex + 1] < _array[leftIndex])
				leftIndex = leftIndex + 1;
			if (leftIndex<_array.size() && _array[prtIndex] > _array[leftIndex])
			{
				swap(_array[prtIndex], _array[leftIndex]);
				prtIndex = leftIndex;
			}
			else
				break;
		}
	}
	void AdjustUp(int  chiIndex)
	{
		int parIndex = (chiIndex - 1) / 2;
		while (chiIndex > 0)//父节点不会小于0，（0-1）/2等于0，此处应用chiIndex来判断
		{
			if (_array[parIndex] > _array[chiIndex])
			{
				swap(_array[parIndex], _array[chiIndex]);
				chiIndex = parIndex;
				parIndex = (chiIndex - 1) / 2;
			}
			else
				break;
		}
	}
protected:
	vector<T> _array;
};

#include"Heap.h"
void Test1()
{
	int array[10] = { 10, 2, 3, 4, 8, 1, 6, 5, 9, 7 };
	Heap<int> h1(array,10);
	h1.Push(0);
	h1.Pop();
	
}

#pragma once
#include<iostream>
#include<vector>
using namespace std;
//仿函数：指一个类满足函数operator,此时是比较大小
template<class T>
struct Great
{
	bool operator()(const T& l, const T& r)
	{
		return l > r;
	}
};
template<class T>
struct Less
{
	bool operator()(const T& l, const T& r)
	{
		return l < r;
	}
};
template<class T,class Comp=Less<int>>
class Heap
{
public:
	//vector调用自己的构造函数
	Heap()
	{}
	Heap(T* a, size_t size)
	{
		for (size_t i = 0; i < size; ++i)
			_array.push_back(a[i]);
		//size-1是数组最大下标，再减1除二是父节点下标
		for (int i = (_array.size() - 1 - 1) / 2; i >= 0; --i)
		{
			AdjustDown(i);
		}
	}
	void Push(const T& x)
	{
		_array.push_back(x);
		AdjustUp(_array.size() - 1);
	}
	void Pop()
	{
		if (_array.size()>0)
		{
			swap(_array[_array.size() - 1], _array[0]);
			_array.pop_back();
			AdjustDown(0);
		}
	}
protected:
	void AdjustDown(int prtIndex)
	{
		int leftIndex = 0;
		while (prtIndex<_array.size())
		{
			leftIndex = prtIndex * 2 + 1;
			//此处应对称方法，传递的参数，比较大小：
			if (leftIndex + 1 < _array.size() && _com(_array[leftIndex + 1] , _array[leftIndex]))
				leftIndex = leftIndex + 1;
			if (leftIndex<_array.size() && _com(_array[leftIndex],_array[prtIndex]))
			{
				swap(_array[prtIndex], _array[leftIndex]);
				prtIndex = leftIndex;
			}
			else
				break;
		}
	}
	void AdjustUp(int  chiIndex)
	{
		int parIndex = (chiIndex - 1) / 2;
		while (chiIndex > 0)//父节点不会小于0，（0-1）/2等于0，此处应用chiIndex来判断
		{
			if (_com(_array[chiIndex], _array[parIndex]))
			{
				swap(_array[parIndex], _array[chiIndex]);
				chiIndex = parIndex;
				parIndex = (chiIndex - 1) / 2;
			}
			else
				break;
		}
	}
protected:
	vector<T> _array;
	Comp _com;
};

void Test2()
{
	int array[10] = { 10, 2, 3, 4, 8, 1, 6, 5, 9, 7 };
	Heap<int,Great<int>> h1(array,10);
	h1.Push(100);
	h1.Pop();
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1752296

Heap，堆，大堆和小堆用仿函数实现

原文：http://10541556.blog.51cto.com/10531556/1752296