C++實現二叉樹及堆的示例代碼

void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環向下調整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標不能越界
		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;//當孩子 >= 父親的時候，滿足小堆的條件，跳出循環節課，否則就會死循環
		}
	}
}

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

//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構建堆,構建堆的時間復雜度是O(n),此時是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構建大堆
	//如果是降序，構建小堆
	//是反著的，因為要和最後一個進行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最後的的元素交換，然後從0到n-2繼續向下調整
		//把次小（次大）的元素也選出來，直到剩最後一個，堆排序完成
		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;

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

#include "Heap.h"
//堆是一種完全二叉樹，用順序存儲（數組）比較好
//用於交換兩個數據
void Swap(HeapDataType* n1, HeapDataType* n2)
{
	HeapDataType temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}
//向下調整算法___老重要瞭，這是理解堆排序和topk問題以及堆這裡相關題的基礎
//向下調整結束的情況有兩個一個是a[parent]<a[child],另一個是從堆頂到數組結束全部比較完
void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下標的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循環向下調整，把最小值（或者最大值浮到堆頂）
	while (child < n)
	{
		//選出左右孩子中較小的孩子，作為child，child+1 < n保證下標不能越界
		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;//當孩子 >= 父親的時候，滿足小堆的條件，跳出循環節課，否則就會死循環
		}
	}
}
//向上調整算法
//用在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;
		}
	}
}
//堆的初始化，內部有堆的創建
void HeapInit(Heap* php, HeapDataType* a, int n)
{
	HeapDataType* temp = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (temp)
	{
		php->arr = temp;
		
	}
	else
	{
		printf("內存申請失敗！");
		exit(-1);
	}
	//將傳進來的數組拷貝給malloc出來的空間，用來後續的堆的創建，刪除，插入數據等操作
	memcpy(php->arr, a, sizeof(HeapDataType)*n);
	php->size = n;
	php->capacity = n;

	//把拷貝進來的數組，構建成堆
	//從倒數第一個非葉子節點進行構建(直接把數組畫成一個完全二叉樹可以直接由圖得到第一個
	//非葉子節點的下標）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->arr, php->size, i);
	}
}
//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是構建堆,構建堆的時間復雜度是O(n),此時是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，構建大堆
	//如果是降序，構建小堆
	//是反著的，因為要和最後一個進行交換
	int end = n - 1;
	while (end>0)
	{
		//把堆頂（最小或者最大）和最後的的元素交換，然後從0到n-2繼續向下調整
		//把次小（次大）的元素也選出來，直到剩最後一個，堆排序完成
		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;
}

//堆的插入數據
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("擴容失敗！\n");
			exit(-1);
		}
	}
	php->arr[php->size++] = x;
	AdjustUp(php->arr, php->size, php->size - 1);
}

//堆的刪除數據,要刪除堆頂的數據
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);
}

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