#include <iostream>
#include <stdlib.h>
using namespace std;
 
/*******************************************/
/*  堆排序
/******************************************/
 
void swap(int &a, int &b)  //位置互換函數
{
	int temp = a;
	a = b;
	b = temp;
}
 
 
void Heap(int array[], int length, int index)  //堆排序算法(大頂堆)
{
	int left = 2 * index + 1;  //左節點數組下標
	int right = 2 * index + 2;  //右節點數組下標
	int max = index;  //index是父節點
 
	if (left < length && array[left] > array[max])  //左節點與父節點比較
	{
		max = left;
	}
	
	if (right < length && array[right] > array[max])  //右節點與父節點比較
	{
		max = right;
	}
 
	if (array[index] != array[max])
	{
		swap(array[index], array[max]);
		Heap(array, length, max);  //遞歸調用
	}
}
 
 
void HeapSort(int array[], int size)  //堆排序函數
{
	for (int i = size / 2 - 1; i >= 0; i--)  // 創建一個堆
	{
		Heap(array, size, i);
	}
 
	for (int i = size - 1; i >= 1; i--)
	{
		swap(array[0], array[i]);  //將array[0]的最大值放到array[i]的位置上，最大值往后靠
		Heap(array, i, 0);  //調用堆排序算法進行比較
	}
}
 
 
int main(void)  //主程序
{
	const int n = 6;  //數組元素的數量
	int array[n];
	cout << "請輸入6個整數：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}
 
	cout << endl;  //換行
 
	HeapSort(array, n);  // 調用HeapSort函數  進行比較
 
	cout << "由小到大的順序排列后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Array" << "[" << i << "]" << " = " << array[i] << endl;
	}
 
	cout << endl << endl;  //換行
 
	system("pause");  //調試時，黑窗口不會閃退，一直保持
	return 0;
}