C++手动实现二叉堆

二叉堆简介

二叉堆是一种特殊的数据结构，它是一颗具有独特优势的二叉树。

简单地说，二叉堆即是一颗父节点与左右子节点间具有严格大小关系的二叉树。其中父节点大于左右子节点的堆被称为最大堆，反之为最小堆。

二叉堆的操作

插入

二叉堆中新元素的插入位置总是最后一个叶子节点所在位置。通过将新节点上浮至合法位置来维持二叉堆的特性。

删除

与插入相对应，二叉堆总是删除当前的根节点，也就是它的堆顶。删掉当前堆顶后，将最后一个叶子节点放在堆顶并下沉至合法位置，以此来维护二叉堆的特性。

构建

二叉堆的构建是从最后一个叶子节点开始，依次通过执行上浮与下沉操作将每一个节点都归位到合法位置的过程。

二叉堆的存储

不同于传统二叉树，二叉堆的存储采用顺序存储，即数组。在不存在左右儿子指针的情况下，假设父节点为parent，那么它的左右儿子分别为2*parent+1与2*parent+2。

#include <bits/stdc++.h>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;
//上浮叶节点 
void upAdjust(vector<int>& arr)
{
	int child = arr.size() - 1;
	int parent = (child - 1)  / 2;
	
	//上浮操作 
	while(child > 0 && arr[child] < arr[parent])
	{
		swap(arr[parent], arr[child]);
		//更新父子下标 
		child = parent;
		parent = (child - 1) / 2;
	}
}
//下沉父节点 
void downAdjust(vector<int>& arr, int parent, int len)
{
	int child = 2 * parent + 1;
	
	while(child < len)
	{
		//如果有右儿子并且右儿子小于左儿子，定位到右儿子
		if(child+1 < len && arr[child+1] < arr[child])
			child = child + 1;
		//如果父节点已经小于任何一个儿子的值，直接跳出
		if(arr[parent] <= arr[child]) break;
		//下沉
		swap(arr[parent], arr[child]);
		parent = child;
		child = 2 * parent + 1; 
	} 
}

void buildHeap(vector<int>& arr)
{
	for(int i = (arr.size()-2)/2; i >= 0; i--)
	{
		downAdjust(arr, i, arr.size());
	}
}

int main()
{
	vector<int> arr;
	int n;
	cin >> n;
	
	while(n--)
	{
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}
	
	cout << "Source arr is:";
	for(int i = 0; i < arr.size(); i++) 
		cout << arr[i] << " ";
	cout << endl;
	
	buildHeap(arr);
	
	cout << "Heap is:";
	for(int i = 0; i < arr.size(); i++) 
		cout << arr[i] << " ";
	
	return 0;
}