void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標(biāo)的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環(huán)向下調(diào)整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標(biāo)不能越界
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//父親比孩子小二者交換位置,并更新迭代孩子的位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代parent child
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//當(dāng)孩子 >= 父親的時(shí)候，滿足小堆的條件，跳出循環(huán)節(jié)課，否則就會(huì)死循環(huán)
		}
	}
}

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構(gòu)建堆,構(gòu)建堆的時(shí)間復(fù)雜度是O(n),此時(shí)是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構(gòu)建大堆
	//如果是降序，構(gòu)建小堆
	//是反著的，因?yàn)橐妥詈笠粋€(gè)進(jìn)行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續(xù)向下調(diào)整
		//把次?。ù未螅┑脑匾策x出來(lái)，直到剩最后一個(gè)，堆排序完成
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

### 3.2.4 堆的的增刪查改
聲明：
```c
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <windows.h>

typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* arr;
	int size;
	int capacity;
} Heap;

//堆的初始化，內(nèi)部有堆的創(chuàng)建
void HeapInit(Heap* php, HeapDataType* a, int n);
//堆的銷毀
void HeapDestory(Heap* php);
//堆的插入數(shù)據(jù)
void HeapPush(Heap* php, HeapDataType x);
//堆的刪除數(shù)據(jù)
void HeapPop(Heap* php);
//獲取堆頂數(shù)據(jù)
HeapDataType HeapTop(Heap* php);
//對(duì)傳入的數(shù)組內(nèi)的數(shù)據(jù)進(jìn)行堆排序
void HeapSort(int* a, int n);

#include "Heap.h"
//堆是一種完全二叉樹，用順序存儲(chǔ)（數(shù)組）比較好
//用于交換兩個(gè)數(shù)據(jù)
void Swap(HeapDataType* n1, HeapDataType* n2)
{
	HeapDataType temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}
//向下調(diào)整算法___老重要了，這是理解堆排序和topk問(wèn)題以及堆這里相關(guān)題的基礎(chǔ)
//向下調(diào)整結(jié)束的情況有兩個(gè)一個(gè)是a[parent]<a[child],另一個(gè)是從堆頂?shù)綌?shù)組結(jié)束全部比較完
void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標(biāo)的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環(huán)向下調(diào)整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標(biāo)不能越界
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//父親比孩子小二者交換位置,并更新迭代孩子的位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代parent child
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//當(dāng)孩子 >= 父親的時(shí)候，滿足小堆的條件，跳出循環(huán)節(jié)課，否則就會(huì)死循環(huán)
		}
	}
}
//向上調(diào)整算法
//用在HeapPush中
void AdjustUp(HeapDataType* a, int n, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的初始化，內(nèi)部有堆的創(chuàng)建
void HeapInit(Heap* php, HeapDataType* a, int n)
{
	HeapDataType* temp = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (temp)
	{
		php->arr = temp;
		
	}
	else
	{
		printf("內(nèi)存申請(qǐng)失敗！");
		exit(-1);
	}
	//將傳進(jìn)來(lái)的數(shù)組拷貝給malloc出來(lái)的空間，用來(lái)后續(xù)的堆的創(chuàng)建，刪除，插入數(shù)據(jù)等操作
	memcpy(php->arr, a, sizeof(HeapDataType)*n);
	php->size = n;
	php->capacity = n;

	//把拷貝進(jìn)來(lái)的數(shù)組，構(gòu)建成堆
	//從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)進(jìn)行構(gòu)建(直接把數(shù)組畫成一個(gè)完全二叉樹可以直接由圖得到第一個(gè)
	//非葉子節(jié)點(diǎn)的下標(biāo)）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->arr, php->size, i);
	}
}
//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構(gòu)建堆,構(gòu)建堆的時(shí)間復(fù)雜度是O(n),此時(shí)是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構(gòu)建大堆
	//如果是降序，構(gòu)建小堆
	//是反著的，因?yàn)橐妥詈笠粋€(gè)進(jìn)行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最后的的元素交換，然后從0到n-2繼續(xù)向下調(diào)整
		//把次小（次大）的元素也選出來(lái)，直到剩最后一個(gè)，堆排序完成
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

//銷毀堆
void HeapDestory(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

//堆的插入數(shù)據(jù)
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		php->capacity *= 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arr, sizeof(HeapDataType)*php->capacity);
		if (tmp)
		{
			php->arr = tmp;
		}
		else
		{
			printf("擴(kuò)容失??！\n");
			exit(-1);
		}
	}
	php->arr[php->size++] = x;
	AdjustUp(php->arr, php->size, php->size - 1);
}

//堆的刪除數(shù)據(jù),要?jiǎng)h除堆頂?shù)臄?shù)據(jù)
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size, 0);
}

//獲取堆頂數(shù)據(jù)
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->arr[0];
}