int array[] = { 27,15,19,18,28,34,65,49,25,37 }; // 根節(jié)點(diǎn)的左右子樹(shù)都是小堆

// 向下調(diào)整算法，建小堆，把大的節(jié)點(diǎn)往下調(diào)整
// 前提是：左右子樹(shù)都是小堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默認(rèn)左孩子最小
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 1. 選出左右孩子最小的那個(gè)，先判斷右孩子是否存在
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++; // 指向右孩子
		}
		// 2. 最小的孩子與父親比較
		if (a[parent] > a[child]) // 如果父親大于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最小的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親小于孩子，說(shuō)明已經(jīng)為小堆了，停止調(diào)整
		{
			break;
		}
	}
}

int a[] = { 1,5,3,8,7,6 };

// 交換函數(shù)
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
// 向下調(diào)整算法，建大堆，把小的節(jié)點(diǎn)往下調(diào)
// 前提是：左右子樹(shù)都是大堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默認(rèn)左孩子最大
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 1. 選出左右孩子最大的那個(gè)，先判斷右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 指向右孩子
		}
		// 2. 最大的孩子與父親比較
		if (a[parent] < a[child]) // 如果父親小于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最大的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親大于孩子，說(shuō)明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}
void HeapSort(int* a, int size)
{
    /* 建堆（大堆）
    * 倒著調(diào)整，從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)的子樹(shù)進(jìn)行向下調(diào)整，直到調(diào)整到根節(jié)點(diǎn)的樹(shù)
    */
	int parent = ((size - 1) - 1) / 2; // 最后一個(gè)葉子節(jié)點(diǎn)的父親的下標(biāo)
	for (int i = parent; i >= 0; i--)  // 從下到上，依次遍歷完所有子樹(shù)，分別對(duì)其進(jìn)行調(diào)整
	{
		AdjustDown(a, size, i);
	}
    /* 堆排序
    * 排升序 --> 建大堆，每次選出一個(gè)最大的數(shù)放到最后
    * 排降序 --> 建小堆，每次選出一個(gè)最小的數(shù)放到最后
    */
    // 下面是排升序：
	int end = size - 1; // 記錄堆中最后一個(gè)元素的下標(biāo)
	while (end > 0)
	{
		Swap(&a[0], &a[end]);  // 將堆頂元素和堆中最后一個(gè)元素交換，把最大的數(shù)(堆頂)放到最后
		AdjustDown(a, end, 0); // 不看最后一個(gè)數(shù)，從根節(jié)點(diǎn)開(kāi)始，對(duì)前面的數(shù)進(jìn)行向下調(diào)整成大堆
		end--;
	}
}

#pragma once
#include<stdio.h>   // printf, perror
#include<stdbool.h> // bool
#include<assert.h>  // assert
#include<stdlib.h>  // malloc, free
#include<string.h>  // memcpy
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a; // 指向動(dòng)態(tài)開(kāi)辟的數(shù)組
	int size;      // 數(shù)組中有效元素個(gè)數(shù)
	int capacity;  // d容量
}Heap;
// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b);
// 向下調(diào)整函數(shù)（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上調(diào)整函數(shù)（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child);
// 初始化堆
void HeapInit(Heap* php, HPDataType* arr, int n);
// 銷毀堆
void HeapDestroy(Heap* php);
// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x);
// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php);
// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php);
// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php);
// 獲取堆中有效元素個(gè)數(shù)
int HeapSize(Heap* php);
// 打印堆
void HeapPrint(Heap* php);

// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
// 向下調(diào)整算法（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent)
{
	// 左孩子下標(biāo)，初始默認(rèn)左孩子最大
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 選出左右孩子最大的那個(gè)，先判斷右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 右孩子最大
		}
		// 最大的孩子與父親比較
		if (a[parent] < a[child]) // 如果父親小于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最大的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親大于孩子，說(shuō)明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}

// 初始化堆，用一個(gè)給定的數(shù)組來(lái)初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
	assert(php); // 斷言
	// 動(dòng)態(tài)開(kāi)辟n個(gè)空間
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	// 把給定數(shù)組的各元素值拷貝過(guò)去
	memcpy(php->a, arr, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	// 建堆(建大堆）
	int parent = ((php->size - 1) - 1) / 2; // 倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)下標(biāo)
	for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹(shù)，分別對(duì)其進(jìn)行調(diào)整
	{
		AdjustDown(php->a, php->size, i);
	}
}

// 銷毀堆
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a); // 釋放動(dòng)態(tài)開(kāi)辟的空間
	php->a = NULL;
	php->size = php->capacity = 0;
}

// 向上調(diào)整算法（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child)
{
	// 父節(jié)點(diǎn)的下標(biāo)
	int parent = (child - 1) / 2;
	//while (parent >= 0) parent不會(huì)小于0
	while (child > 0)
	{
		// 孩子與父親進(jìn)行比較
		if (a[child] > a[parent]) // 如果孩子大于父親
		{
			// 孩子與父親交換
			Swap(&a[child], &a[parent]);

			// 更新父子下標(biāo)，原先父親作為孩子，繼續(xù)往上調(diào)
			child = parent;
			parent = (child - 1) / 2;
		}
		else // 如果孩子小于父親，說(shuō)明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}

// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x)
{
	assert(php);
	// 先檢查空間是否已滿
	if (php->capacity == php->size)
	{
		// 增容兩倍
		php->capacity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);
		if (tmp != NULL)
		{
			php->a = tmp;
			tmp = NULL;
		}
	}
	// 插入元素
	php->a[php->size] = x;
	php->size++;
	// 從插入的元素開(kāi)始，進(jìn)行向上調(diào)整，保持它依然是堆
	AdjustUp(php->a, php->size - 1);
}

// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能為空
	// 將堆頂元素和最后一個(gè)元素交換
	Swap(&php->a[0], &php->a[php->size - 1]);
	// 刪除堆中最后一個(gè)元素
	php->size--;
	// 從根節(jié)點(diǎn)開(kāi)始，對(duì)剩下元素進(jìn)行向下調(diào)整成大堆，保持它依然是堆
	AdjustDown(php->a, php->size, 0);
}

// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能為空
	return php->a[0];
}

// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

void TestHeap()
{
	int a[] = { 1,5,3,8,7,6 };
	Heap hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(a[0])); // 初始化堆
	int k = 0;
	scanf("%d", &k);
	printf("找出堆中前%d個(gè)最大元素：\n", k);
	while (!HeapEmpty(&hp) && k--)
	{
		printf("%d ", HeapTop(&hp)); // 獲取堆頂元素
		HeapPop(&hp); // 刪除堆頂元素
	}
	printf("\n");
}

// 向上調(diào)整算法建堆
void CreateHeap(int* a, int size)
{
	// 把第一個(gè)元素看作是堆，剩余的元素依次插入堆中
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}
}