#include "string"#include "vector"#include "time.h"typedef std::basic_string<TCHAR> tstring;typedef std::vector<int> IntVec;// iIndexAdjust 从0计数.... left = 2i+1;right = 2i+2// 最后一个非叶子节点  (iHeapTreeSize - 2) / 2// iHeapTreeSize 无序堆大小(无序区节点数)void HeapifyMax(IntVec & iHeapTree,int const iIndexAdjust,int const iHeapTreeSize){	if (iIndexAdjust > (iHeapTreeSize - 2) / 2)//只针对非叶子节点		return;	int iIndexGreater = iIndexAdjust;		int child = 2 * iIndexAdjust + 1;	if (child < iHeapTreeSize && iHeapTree[child] > iHeapTree[iIndexGreater])		iIndexGreater = child;	child = 2 * iIndexAdjust + 2;	if (child < iHeapTreeSize && iHeapTree[child] > iHeapTree[iIndexGreater])		iIndexGreater = child;	if (iIndexAdjust == iIndexGreater)		return;	std::swap(iHeapTree[iIndexAdjust], iHeapTree[iIndexGreater]);	HeapifyMax(iHeapTree, iIndexGreater, iHeapTreeSize);//重新修正子树}// 从最后一个非叶子节点开始构建void HeapBuild(IntVec & iHeapTree){	for (int i = (iHeapTree.size() - 2) / 2; i >= 0; i--){		HeapifyMax(iHeapTree, i,iHeapTree.size());	}}void HeapSort(IntVec & iHeapTree){	for (int i = iHeapTree.size() - 1; i >= 0; i--)	{		std::swap(iHeapTree[0], iHeapTree[i]);		HeapifyMax(iHeapTree, 0, i); // 最后一个参数 HeapBuild时是 iHeapTree.size(),交换一次根,少一个节点	}}void HeapPrint(IntVec & iHeapTree){	for (auto i:iHeapTree){		printf("%d ", i);	}	printf("\n");}int _tmain(int argc, _TCHAR* argv[]){	srand((unsigned int)time(0));	IntVec ints;	for (int i = 0; i < 20; i++){		ints.push_back(rand() % 100);	}	printf("arr init\n");HeapPrint(ints);		HeapBuild(ints);	printf("arr after build \n"); HeapPrint(ints);	HeapSort(ints);	printf("arr after sort \n"); HeapPrint(ints);	return 0;}

arr init74 51 18 91 59 88 48 16 76 23 17 64 52 82 30 67 52 5 93 12arr after build93 91 88 76 59 64 82 67 74 23 17 18 52 48 30 16 52 5 51 12arr after sort5 12 16 17 18 23 30 48 51 52 52 59 64 67 74 76 82 88 91 93