堆操作

需要知道的：

堆肯定就是完全二叉树
如果双亲结点为在数组的下标i，那么左右孩子结点分别为：2*i+1、2*i+2
如果孩子结点为j，那么其双亲结点为(j-1)/2

构建堆结构、删除堆元素进行【下沉】操作

插入元素进行【上浮】操作

如何将该数组构建成一个小顶堆结构？

int arr[] = {15,12,17,30,50,20,60,65,4,19};

原始结构：

第一步：取原始的堆结构中的最后一个非叶子结点【i】，将【i】和【2*i+1】和【2*i+2】的元素进行比较，如果有比【i】元素小的，进行交换，并将较小的孩子结点下标设置为当前要比对的结点下标，直到对于【i】满足了小顶堆或者到了叶子结点停止，这个操作也就是【下沉】操作

构建过程如图：

核心就是寻找到每个非叶子结点的在小顶堆中的正确的位置 

代码如下：

template <class T>
void Heap<T>::FilterDown(int i)
{
	int  currentPos = i;
	int childPos = 2 * i + 1;
	T target = hList[currentPos];
	//如果中间过程没有满足堆条件，一直比对到最后一层的叶子结点
	while (childPos < heapSize)
	{
		//将当前结点和孩子较小结点元素比对
		if (childPos + 1 < heapSize && hList[childPos + 1] < hList[childPos])
			childPos = childPos + 1;
		//当前结点小于其孩子结点，以满足小顶堆，找到正确位置
		if (target <= hList[childPos])
			break;
		else
		{
			hList[currentPos] = hList[childPos];
			currentPos = childPos;
			childPos = currentPos * 2 + 1;
		}
	}
	hList[currentPos] = target;
}

 依次对原始数组中的每个元素（从最后一个非叶子结点往堆顶【0】的顺序）进行【下沉操作】，最终构建成一个小顶堆结构（大顶堆也是同样操作，只是比较更大的孩子元素进行交换）

	//最后一个堆元素的索引为 n-1，那么其双亲索引为(n-1-1)/2 = (n-2)/2
	currentPos = (heapSize - 2) / 2;    //heapSize为数组的大小
	//依次对每个非叶子结点进行下沉操作
	while (currentPos >= 0)
	{
		FilterDown(currentPos);
		currentPos--;
	}

插入元素：将插入元素放入扩充数组尾部位置，进行【上浮】寻找合适的位置

在小顶堆中插入元素8，因为该结构已经是小顶堆了，所以只需要进行上浮找到合适位置即可

template <class T>
void Heap<T>::Insert(const T& item)
{
	if (heapSize == maxHeapSize)
	{
		cout << "Heap full";
		return;
	}
		//将元素存入堆尾，并使堆大小+1，并调用FilterUp()将该元素上浮寻找正确位置
		hList[heapSize] = item;
		heapSize++;
		FilterUp(heapSize);
}

template <class T>
void Heap<T>::FilterUp(int i)
{
	//curretnPos 为遍历双亲路径上的下标，target为hList[i]的值，并被重新安置在路径中
	int currentPos = i;
	int parentPos = (i - 1) / 2;
	T target = hList[i];
	//沿双亲路径到根
	while (currentPos != 0)
	{
		//当前下标位置已经满足小顶堆条件，无须往上比对了
		if (hList[parentPos] <= target)
			break;
		else
		{
			//当前结点的值要比双亲结点小，继续往上找位置
			hList[currentPos] = hList[parentPos];		//双亲结点元素下移
			currentPos = parentPos;
			parentPos = (currentPos - 1) / 2;
		}
	}
	//找到了当前结点的正确位置
	hList[currentPos] = target;
}

删除元素：

首先将要被删除的元素（不论堆顶还是堆内的元素）和数组的尾元素进行交换，并将堆的可操作大小减-1，然后堆被删除的下标元素进行【下沉】，找到其在堆中的正确位置

例如：删除堆顶元素4之后的结构如图

//返回堆中第一个元素并修改堆
template<class T>
T Heap<T>::Delete()
{
	T tempItem;
	if (heapSize == 0)
	{
		cout << "Heap empty";
		return -1;
	}
		
	//删除堆顶元素，并将最后一个元素放在堆顶位置，并对该元素进行下沉到正确位置使满足小顶堆
	tempItem = hList[0];
	hList[0] = hList[heapSize - 1];
	heapSize--;
	FilterDown(0);			//堆顶元素下沉到合适位置
	return tempItem;		//返回堆顶元素
}

堆排序：就是不断删除堆顶元素

//堆排序的算法复杂度为：O(nlog2n)
template <class T>
void Heap<T>::HeapSort(T a[],int n)
{
	T element;
	for (int i=0;i<n;i++)
	{
		element = this->Delete();
		a[i] = element;
	}
}