堆

定义与基本操作

定义

• 堆是一棵完全二叉树，每个节点的值都不大于(小顶堆)或者不小于(大顶堆)其左右节点的值
• 堆一般用于优先队列的实现

基本操作

如果用数组来存储一棵完全二叉树，根节点存储在1号位置，则第i号位表示的节点的左子树和右子树分别为2i和2i+1

• 向下调整

将当前节点和其左右子节点进行比较，如果子节点的值存在大于当前节点的值，则将权值中较大的子节点的值和当前节点的值进行交换；
继续比较当前节点和其子节点，直到子节点的值都小于当前节点的值，代码如下：

void downAdjust(int low,int high)
{
	int i=low,j=i*2;
	while(j<=high)
	{
		if(j+1<=high && heap[j+1]>heap[j])
		{
			j=j+1;
		}
		if(heap[j]>heap[i])
		{
			swap(heap[j],heap[i]);
			i=j;
			j=i*2;
		}
		else
		{
			break;
		}
	}
}

• 向上调整

和向下调整相反，向上调整总是将欲调整的元素和其父节点比较，代码如下：

void upAdjust(int low,int high)
{
	int i=high,j=i/2;
	while(j>=low)
	{
		if(heap[j]<heap[i])
		{
			swap(heap[j],heap[i]);
			i=j;
			j=i/2;
		}
		else
		{
			break; 
		}
	}
}

• 建堆

二叉树中元素个数为n,完全二叉树叶子节点个数为n/2，因此下标[1,n/2]范围内都是非叶子节点。
代码如下：

void creatHeap()
{
	for(int i=n/2;i>=1;i--)
	{
		downAdjust(i,n);
	}
}

• 删除元素

以删除堆定元素为例，代码如下：

void deleteTop()
{
	heap[1]=heap[n--];
	downAdjust(1,n);
}

• 添加元素

在数组的末尾添加一个元素，然后向上调整新加入的节点，代码如下：

void insert(int x)
{
	heap[++n]=x;
	upAdjust(1,n);
}

• 堆排序

void heapSort()
{
	creatHeap();
	for(int i=n;i>1;i--)
	{
		swap(heap[i],heap[1]);
		downAdjust(1,i-1);
	}
}