// DUIPAIXU.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define MAXSIZE  100 // 待排順序表最大長度
typedef  int  KeyType;    // 關鍵字類型為整數類型
typedef  struct {
     KeyType   key;              // 關鍵字項
} RcdType;                         // 記錄類型
typedef  struct {
     RcdType r[MAXSIZE + 1];   // r[0]閑置
     int length;                   // 順序表長度
} SqList;   // 順序表類型
typedef  SqList  HeapType;
HeapType H1;     
void Creat(SqList &L,int n)
{
	L.length = n + 1;
	int i = 0,l = 0;
	L.r[i].key = 0;
	for(i = 1;i < L.length;i++)
	{
		printf("請輸入靜態表元素[%d]:",i);
		scanf("%d",&l);
		L.r[i].key = l;
	}
}
void Swap(RcdType &a,RcdType &b)
{
	RcdType t;
	t = a;
	a = b;
	b = t;
}
void HeapAdjust (HeapType &H, int s, int m)// 已知 R[s..m]中記錄的關鍵字除 R[s] 之外均滿足堆的特征，本函數自上而下調整 R[s] 的關鍵字，使 R[s..m] 也成為一個大頂堆
{    
	int j = 0;
	RcdType rc;
	rc = H.r[s];                         // 暫存 R[s] 
	for(j = 2 * s;j <= m;j *= 2 ) // j 初值指向左孩子自上而下的篩選過程;
	{  
		if (j < m && H.r[j].key < H.r[j + 1].key )  
			++j;     // 左/右“子樹根”之間先進行相互比較
		if (rc.key >= H.r[j].key )  
			break; // 再作“根”和“子樹根”之間的比較，若“>=”成立，則說明已找到 rc 的插入位置 s ，不需要繼續往下調整令 j 指示關鍵字較大記錄的位置
		H.r[s] = H.r[j];  
		s = j;   // 否則記錄上移，尚需繼續往下調整
	}
	H.r[s] = rc;       // 將調整前的堆頂記錄插入到 s 位置
} // HeapAdjust

void HeapSort(HeapType &H)  //對順序表H進行堆排序
{ 
	int i = 0;
	for (i = H.length / 2;i > 0;--i)  //把H.r[1..H.Length]建成大堆頂
		HeapAdjust(H,i,H.length);
	for (i = H.length;i > 1;--i)
	{
		Swap(H.r[1],H.r[i]);     //將堆頂記錄和當前未經排序子序列H.r[1..i]中最后一個記錄相互交換;
		HeapAdjust(H,1,i-1);  //將H.r[1..i-1]重新調整為大堆頂
    }
}

int main(int argc, char* argv[])
{
	int length = 0;
	printf("請輸入靜態表長度:\n");
	scanf("%d",&length);
	Creat(H1,length);
	HeapSort(H1);
    printf("排序后的結果為:\n");
	for(int i = 1;i < H1.length;i++)
	{
		printf("%4d",H1.r[i]);
	}
	printf("\n");
	return 0;
}