二叉树1建堆调整

二叉树的调整，建堆
//二叉树
//使用数组顺序存储二叉树
//二叉树的另一种存放形式就是使用堆来实现
//堆一般用来求解的是最值问题。堆分为大堆小堆两种情况，这里涉及二叉树的删除的操作
//其实就是堆的情况就是会使用的是数组来进行存放，依次由小到大。
//向下调整，调整就是要保证子结构是堆，再就是表示的是如果现在不是的话就得进行遍历。
//向下调整：
//1.从左右孩子中选择一个最小值
//2.当前需要调整的数据和最小值进行比较
//大于最小值：和最小值进行交换，从调整的位置继续执行第一步
//小于等于最小值；结束调整。

//假设为小堆
void shiftDown(int* arr, int n, int curPos)
{
//左孩子
int child = 2 * curPos + 1;
while (child < n)
{
//从左右孩子中找到一个最小值的位置
if (child+1 ++child;
//需要调整的数据和最小值进行比较
if (arr[child] < arr[curPos])
{
int tmp = arr[child];
arr[child] = arr[curPos];
arr[curPos] = tmp;

			//更新位置
			curPos = child;
			child = 2 * curPos + 1;
		}
	   else
		   break;
}

}

//假设为大堆（子结构是大堆）现在也是一个向下调整的过程
void shiftDown(int* arr, int n, int curPos)
{
//左孩子
int child = 2 * curPos + 1;
while (child < n)
{
//从左右孩子中找到一个最大值的位置
if (child + 1 < n && arr[child + 1]> arr[child])
++child;
//需要调整的数据和最大值进行比较
if (arr[child] > arr[curPos])
{
int tmp = arr[child];
arr[child] = arr[curPos];
arr[curPos] = tmp;

		//更新位置
		curPos = child;
		child = 2 * curPos + 1;
	}
	else
		break;
}

}

void test1()
{
int arr[] = { 10,5,3,8,7,6 };
shiftDown(arr, sizeof(arr) / sizeof(arr[0]), 0);
}

void test2()
{
int arr[] = { 7,56,30,25,15,10 };
shiftDown(arr, sizeof(arr) / sizeof(arr[0]), 0);
}
int main()
{
test1();
test2();
test();
return 0;
}

//建堆
//小堆–>大堆
//调整的过程 首先是确定的是确保左右子结构是堆才是可以进行继续操作
//调整的就是最后一个非叶子结点开始进行向下调整。
//向下调整的次数是和非叶子结点个数是相同的。
//最后一个非叶子结点的位置（索引）；
//（n-2）/2

void creatHeap(int* arr, int n)
{
//从最后一个非叶子开始向下调整
for (int i = (n - 2) / 2; i >= 0; --i)
{
//shiftDown(数组指针，数组元素个数，调整的起始位置)
shiftDown(arr, n, i);
}
}

void test()
{
int arr[] = { 100,20,3,6,89,12,15,36,25 };
creatHeap(arr, sizeof(arr) / sizeof(arr[0]));
}