堆的结构分析与应用

    在二叉树中，我们用两种方法表示二叉树，一个是链表，一个是数组，但是数组比较适用于满二叉树或者完全二叉树。

创新互联公司是一家集网站建设,石阡企业网站建设,石阡品牌网站建设,网站定制,石阡网站建设报价,网络营销,网络优化,石阡网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

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

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

        最大堆：每个父节点的都大于孩子节点。

        最小堆：每个父节点的都小于孩子节点。

#include
#include
#include

using namespace std;

template
class Heap
{
public:
	Heap()//无参类型的构造函数
	{}
	Heap(T *a, size_t size)//有参类型的构造函数
	{
		assert(a);
	
		for (size_t i = 0; i < size; i++)
		{
			_a.push_back(a[i]);
		}
		//建堆，用 向下调整 算法
		//对于一个完全二叉树，其结点的父子关系与数组的下标的关系：
		//左子下标= 父结点下标*2+1
		//右子下标=父结点下标*2+2
		for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点（最后一个元素一定是非叶子结点的子节点）
		{
			_AdjustDown(j);
		}
		/*
		在第一次写时定义了j为size_t类型，由于j不管怎么运算都是无符号类型所以
		j>=0并没有起到限制的作用，导致了死循环
		*/
	}
public:
	void Push(const T &x)//在最后加入一个节点
	{
		_a.push_back(x);
		_AdjustUp(_a.size() - 1);//向上调整，传入最后一个元素下标（调整x的位置）
	}
	
	void Pop()//把最大的删掉（根）
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
		_a.pop_back();//删掉最后一个节点
		_AdjustDown(0);//向下调整
	}
	
	void Print()
	{
		for (size_t i = 0; i < _a.size(); i++)
		{
			cout << _a[i]<<" ";
		}
		cout << endl;
	}
	size_t size()
	{
		return _a.size();
	}
	bool empty()
	{
		return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
	{
		size_t child = parent * 2 + 1; //找到其左孩子
		while (child < _a.size())
		{
			if ((child + 1) < _a.size() && _a[child] < _a[child + 1])//若左孩子小于右孩子（且必须结点下标不超过范围）
			{
				++child;//指向大的
			}
			if (_a[child]>_a[parent])//若孩子大于父，则把大的放在父结点上
			{
				swap(_a[child], _a[parent]);
				parent = child;//父和子调整后要继续向下调整交换后的子节点
				child = parent * 2 + 1;//现在这个调整后的节点的子节点
			}
			else
				break;
		}
	}
	
	void _AdjustUp(size_t child)//时间复杂度O(log2(N))
	{
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_a[child] > _a[parent])
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
		
	}
private:
	vector _a;
};

测试函数

void test()
{
	int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	Heap h2(a, 10);
	h2.Push(3);
	h2.Push(4);
	h2.Print();
	h2.Push(100);
	h2.Print();
	h2.Pop();
	h2.Print();
	h2.Pop();
	h2.Print();

}
int main()
{
	test();
	getchar();
	return 0;
}

    上面实现了最大堆，最小堆方法同最大堆，但是再在类中重新一遍则会使程序的可维护性降低，所以我们用仿函数来实现。

仿函数

仿函数就是使一个类使用看上去像一个函数，其实现就是类中实现一个operator().这个类就有了类似函数的行为。

用仿函数实现最大堆与最小堆

template
struct Less
{
	bool operator()(const T&left, const T&right)
	{
		return left < right;
	}
};
template
struct Greater
{
	bool operator()(const T&left, const T&right)
	{
		return left>right;
	}
};

template>
class Heap
{
public:
	Heap()//无参类型的构造函数
	{}
	Heap(T *a, size_t size)//有参类型的构造函数
	{
		assert(a);
	
		for (size_t i = 0; i < size; i++)
		{
			_a.push_back(a[i]);
		}
		//建堆，用 向下调整 算法
		//对于一个完全二叉树，其结点的父子关系与数组的下标的关系：
		//左子下标= 父结点下标*2+1
		//右子下标=父结点下标*2+2
		for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点（最后一个元素一定是非叶子结点的子节点）
		{
			_AdjustDown(j);
		}
	}
public:
	void Push(const T &x)//在最后加入一个节点
	{
		_a.push_back(x);
		_AdjustUp(_a.size() - 1);//向上调整，传入最后一个元素下标（调整x的位置）
	}
	void Pop()//把最大的删掉（根）
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
		_a.pop_back();//删掉最后一个节点
		_AdjustDown(0);//向下调整
	}
	void Print()
	{
		for (size_t i = 0; i < _a.size(); i++)
		{
			cout << _a[i]<<" ";
		}
		cout << endl;
	}
	size_t size()
	{
		return _a.size();
	}
	bool empty()
	{
		return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
	{
		size_t child = parent * 2 + 1; //找到其左孩子
		compare com;
		while (child < _a.size())
		{
			if ((child + 1) < _a.size() && com(_a[child+1],_a[child]))
			{
				++child;
			}
			if (com(_a[child],_a[parent]))//
			{
				swap(_a[child], _a[parent]);
				parent = child;//父和子调整后要继续向下调整交换后的子节点
				child = parent * 2 + 1;//现在这个调整后的节点的子节点
			}
			else
				break;
		}
	}
	void _AdjustUp(size_t child)//时间复杂度O(log2(N))
	{
		size_t 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;
		}
		
	}
private:
	vector _a;
};

    这样就实现了最大堆与最小堆，通过仿函数，程序的可维护性好于在类中写一个最大堆写法和最小堆写法。

测试

void test1()
{
	int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
	Heap> h2(a, 10);//最小堆
	h2.Push(3);
	h2.Push(4);
	h2.Print();
	h2.Push(100);
	h2.Print();
	h2.Pop();
	h2.Print();
	h2.Pop();
	h2.Print();
	
	Heaph3(b);//最大堆
        h3.Push(3);
	h3.Push(4);
	h3.Print();
	h3.Push(100);
	h3.Print();
	h3.Pop();
	h3.Print();
	h3.Pop();
	h3.Print();
}

堆的应用：

1.堆排序

分析：由于在大堆或者小堆排完后，只能保证每个小树为大堆或者小堆，故还需要进行排序才能使数组元素完全依次排列。

      所以我们先用大堆排列后，使堆顶元素为大元素，再依次将堆顶元素和未交换的最后一个元素交换，交换完成后再将除了大的元素之外的元素进行交换

/******************************
堆排序
尽建立一个大堆，每次把堆顶的元素和最后一个还未交换的元素交换
*/
void AdjustDown(int *a, int parent, int size)
{
	int child = parent * 2 + 1;
	
	while (child < size)
	{
		if (a[child] a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;

	}
}
void HeapSort(int *a, int n)
{
	assert(a);

	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a,i,n);//大堆向下调整
	}
	
	for (int i = 0; i < n; i++)
	{
		swap(a[n - 1 - i],a[0]);
		AdjustDown(a, 0, n - 1 - i);
	}

}

2.求N个元素中前K个最大的数

    分析：建立一个小堆存放前K个元素，小堆的堆顶元素为前K个中最小的值，剩下N-K个数中依次和堆顶元素相比较，若大于堆顶元素，入堆，每入堆一个元素再小堆排序一次，使堆顶元素总为这K个元素的最小值；若小于堆顶元素，则继续下一个数比较。当N-K个元素全比较完，堆中这K个元素就是最大的前K个数。

/*
从N个数中找到K个最大的数
建立一个小堆，大小为K,每次从第N-K的数据中取出一个和堆顶元素比较
*/
const int N = 1000000;
const int K = 100;

void AdjustDown(int *a, int parent, int size)
{
	int child = parent * 2 + 1;
	while (child  a[child + 1])
		{
			child++;
		}
		
		if (a[child] < a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void GetTopK(int *a)
{
	assert(K < N);
	int top[100];

	for (size_t i = 0; i < 100; i++)
	{
		top[i] = a[i];
	}
	//建一个小堆，向下调整
	for (int i = (K - 2) / 2; i>=0; i--)
	{
		AdjustDown(top, i, K);
	}
	//从剩下的N-K的数据中拿数据和堆顶元素比较，若小于堆顶元素，则入堆
	for (size_t j = K; j < N ; j++)
	{
		if (a[j]            
            
                        

            分享名称：堆的结构分析与应用            

            文章URL：http://cqcxhl.com/article/jsgjhe.html