C/C++堆

• 1. 堆的定义
• 2. 堆的建立
• • 2.1 堆元素向上调整
  • 2.2 测试程序
• 3. 堆元素删除
• • 3.1 堆元素向下调整
  • 3.2 测试程序

  对于一棵二叉树，当每个节点都大于等于它的两个子节点时，称为堆有序，这样的堆称为大堆；而当每个节点都小于等于它的两个子节点时，称为小堆。堆可以用一个数组表示：

思路：每次插入一个数，就对数组作调整。[8, 15, 11, 48, 7, 24, 2, 19, 21, 47, 45, 5, 25, 38, 23]

• 若建立大堆，则将插入的数与父节点比较，若大于父节点，则交换元素后向上调整；若小于父节点不作调整。
• 若建立小堆，则将插入的数与父节点比较，若小于父节点，则交换元素后向上调整；若大于父节点不作调整。
• 数组中，对于一个子节点查找其父节点的方法：parent = (child - 1) / 2，其中parent和child分别为父亲和孩子的下标。

//********************** 向上调整 **********************
template
void HeapAdjustUp(std::vector& vec, int cur, Compare comp)
{
	int parent = (cur - 1) / 2;
	while (cur > 0) //注意这非parent >= 0, cur 为0的情况死循环
	{
		if (comp(vec[cur], vec[parent]))
		{
			Swap(vec[cur], vec[parent]);
			cur = parent;
			parent = (cur - 1) / 2;
		}
		else
			break;
	}
}

//********************** 建立堆_逐一插入 **********************
template
void HeapCeate(std::vector& vec, const T& x, Compare comp)
{
	vec.push_back(x);
	HeapAdjustUp(vec, vec.size() - 1, comp);
}
//***********************************************************

#include 
#include 
#include 

template
inline void Swap(DataType& a, DataType& b)
{
	DataType tmp = a;
	a = b;
	b = tmp;
}


template
struct MinHeap
{
	bool operator()(const T& x, const T& y)
	{
		return x <= y;
	}
};

template
struct MaxHeap
{
	bool operator()(const T& x, const T& y)
	{
		return x >= y;
	}
};

int main()
{
	std::vector vec;
	int a[] = {8, 15, 11, 48, 7, 24, 2, 19, 21, 47, 45, 5, 25, 38, 23};
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapCeate(vec, a[i], MaxHeap());
	}
	for (int i = 0; i < vec.size(); i++)
	{
		std::cout << vec[i] << " ";
	}
	return 0;
}

结果显示：

思路：将最后一个元素和堆顶元素交换，然后调整顺序。以下用cur表示堆顶元素

• 大堆：将cur与左右孩子中值大的比较，若cur < ChildMax , 则交换元素，将cur指向ChildMax 并继续向下调整；否则结束。
• 大堆：将cur与左右孩子中值小的比较，若cur > ChildMin, 则交换元素，将cur指向ChildMax 并继续向下调整；否则结束。
• 数组中，对于一个父节点查找器子节点的方法：左孩子childL = 2 * parent + 1；右孩子childR = 2 * parent + 2

//********************** 向下调整 **********************
template 
void HeapAdjustDown(std::vector& vec, int cur, Compare comp)
{
	int childL = cur * 2 + 1; // 得到左孩子的下标
	//int childR = childL + 1; // 得到右孩子的下标
	int size = vec.size();

	while (childL < size)  // 叶子节点没有左孩子
	{
		if (childL + 1 < size && comp(vec[childL + 1], vec[childL])) // 保证有孩子存在；若右孩子较大，则选出右孩子
			childL++;

		if (comp(vec[childL], vec[cur]))  //大堆 ，将小的元素向下调整
		{
			Swap(vec[childL], vec[cur]);
			cur = childL;
			childL = cur * 2 + 1;
		}
		else // 父亲比小孩子小
			break;
	}
}

//********************** 删除堆顶元素 **********************
template
void HeapDeleteElement(std::vector& vec, Compare comp)
{
	Swap(vec[0], vec[vec.size() - 1]);
	vec.pop_back();
	HeapAdjustDown(vec, 0,comp);
}

int main()
{
	srand((unsigned int)time(nullptr));
	std::vector vec;
	int a[] = {8, 15, 11, 49, 7, 24, 2, 19, 21, 47, 45, 5, 25, 38, 23};
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapCeate(vec, a[i], MaxHeap());
	}
	for (int i = 0; i < vec.size(); i++)
	{
		std::cout << vec[i] << " ";
	}
	std::cout << std::endl;
	HeapDeleteElement(vec,  MaxHeap());
	for (int i = 0; i < vec.size(); i++)
	{
		std::cout << vec[i] << " ";
	}
	return 0;
}

结果显示：