typedef struct
{
	int data;
	int parent;   // 雙親位置
}PtNode;
typedef struct
{
	PtNode nodes[10];
	int root ;  
	int n;

}PTree;

typedef struct CSNode
{
	int data;
	struct CSNode* firstchild, * rightsib;
};

  假設(shè)父親的結(jié)點(diǎn)序號(hào)為parent，左孩子為leftchild，右孩子為ringhtchild。
  有： leftchild=parent*2+1
          rightchild=parent*2+2

#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
	
	int child = 2 * parent + 1;//套用公式可得
	
	while (child < n)
	{
		if (child+1<n&&a[child] > a[child + 1])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
				parent = child;
		child = 2 * parent + 1;
		}
	
		else
		{
			break;
		}
	}
}
int main()
{
	int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
	int n = 14;
	 AdjustDown(arr, n, 0);
	return 0;
}

#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
	
	int child = 2 * parent + 1;
	
	while (child < n)
	{
		if (child+1<=n && a[child] >a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
	int n = 14;
	 
	int tmp = 0;
	int i = (n - 1 - 1) / 2;
	for (i; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
	return 0;
}

#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
	
	int child = 2 * parent + 1;
	
	while (child < n)
	{
		if (child+1<n && a[child] <a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
	int n =14 ;
	 
	int tmp = 0;
	int i = (n - 1 - 1) / 2;
	for (i; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		int tmp = arr[0];
		arr[0] = arr[end];
		arr[end] = tmp;
		AdjustDown(arr, end, 0);
		end--;
	}
	return 0;
}

void AdjustUp(int* a, int n, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 * Note: The returned array must be malloced, assume caller calls free().
 */
/* 交換 */
void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 從堆下層向上交換元素，使得堆為大根堆 */
void swim(int* nums, int k) {
    while (k > 1 && nums[k] > nums[k / 2]) {
        swap(&nums[k], &nums[k / 2]);
        k /= 2;
    }
}

/* 從堆上層向下層交換元素，使得堆為大根堆 */
void sink(int* nums, int k, int numsSize) {
    while (2 * k < numsSize) {
        int child = 2 * k;
        if (child < numsSize && nums[child] < nums[child + 1]) {
            child++;
        }
        if (nums[k] > nums[child]) {
            break;
        }
        swap(&nums[k], &nums[child]);
        k = child;
    }
}

/* 定義堆的結(jié)構(gòu)體 */
typedef struct Heap {
    int* data;
    int szie;
    int capacity;
}T_Heap, *PT_Heap;

/* 初始化一個(gè)堆 */
PT_Heap createHeap(int k) {
    PT_Heap obj = (PT_Heap)malloc(sizeof(T_Heap));
    obj->data = (int*)malloc(sizeof(int) * (k + 1));
    obj->szie = 0;
    obj->capacity = k + 1;
    return obj;
}

/* 判斷堆是否為空 */
bool isEmpty(PT_Heap obj) {
    return obj->szie == 0;
}

/* 獲得堆的當(dāng)前大小 */
int getHeapSize(PT_Heap obj) {
    return obj->szie;
}

/* 將元素入堆 */
void pushHeap(PT_Heap obj, int elem) {
    /* 新加入的元素放入堆的最后 */
    obj->data[++obj->szie] = elem;
    /* 對(duì)當(dāng)前堆進(jìn)行排序,使其成為一個(gè)大根堆 */
    swim(obj->data, obj->szie);
}

/* 獲得堆頂元素 */
int getHeapTop(PT_Heap obj) {
    return obj->data[1];
}

/* 將堆頂元素出堆 */
int popHeap(PT_Heap obj) {
    /* 保存堆頂元素 */
    int top = obj->data[1];
    /* 將堆頂元素和堆底元素交換,同時(shí)堆長(zhǎng)度減一 */
    swap(&obj->data[1], &obj->data[obj->szie--]);
    /* 將原先的堆底元素賦值為INT_MIN */
    obj->data[obj->szie + 1] = INT_MIN;
    /* 從堆頂開始重新堆化 */
    sink(obj->data, 1, obj->szie);
    return top;
}

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
    /* 若數(shù)組為空、或k為0，返回NULL */
    if (arrSize == 0 || k == 0) {
        *returnSize = 0;
        return NULL;
    } else {
        *returnSize = k;
    }
    /* 返回?cái)?shù)組長(zhǎng)度為k */
    int* ret = (int*)calloc(k, sizeof(int));
    /* 初始化一個(gè)大小為k的堆 */
    PT_Heap heap = createHeap(k);
    /* 將輸入數(shù)組前k個(gè)元素堆化 */
    for (int i = 0; i < k; i++) {
        pushHeap(heap, arr[i]);
    }
    /* 將輸入數(shù)組剩下的元素依次插入堆，得出最小的k個(gè)數(shù) */
    for (int i = k; i < arrSize; i++) {
        if (arr[i] < getHeapTop(heap)) {
            popHeap(heap);
            pushHeap(heap, arr[i]);
        }
    }
    /* 將堆中元素傳入返回?cái)?shù)組 */
    for (int i = 0; i < k; i++) {
        ret[i] = popHeap(heap);
    }
    return ret;
}

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	printf(" %c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	InOrder(root->left);
	printf(" %c ", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	const BTNode* a = root;
                                                                                                                                                                                                                                                                                                                                                                              	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf(" %c ", root->data);
}