寫得還算認(rèn)真，本來覺得自己已經(jīng)懂了，動(dòng)手的時(shí)候才知道細(xì)節(jié)上好多不清楚。看來以后要多動(dòng)手了，汗

/*
*???FILE:???????????heap.c
*???DATA:???????????2006.7.11
*???AUTHOR:?????????Liu?Qi
*???DESCRIPTION:????heap?demo
*/


#include?"../common/config.h"
#include?"heap.h"


#define?LeftChild(r)?((r)?*?2?+?1)


void?heapify(ElemType?arr[],?int?heapSize,?int?root)
{
????while?(?!isLeaf(root,?heapSize))????//非葉節(jié)點(diǎn),必有左孩子
????{
????????int?maxChild?=?LeftChild(root);
????????//有右孩子，并且右孩子大于左孩子
????????if?(?maxChild?<?heapSize?-?1?&&?arr[maxChild]?<?arr[maxChild?+?1])
????????????????maxChild++;?//取右孩子
????????//沒有右孩子
????????if?(?arr[root]?>=?arr[maxChild]?)???//根比孩子大，不用調(diào)整
????????????return;

????????swap(?&arr[root],?&arr[maxChild]?);
????????root?=?maxChild;
????}
}

void?MakeHeap(ElemType?arr[],?int?len)
{
????int?i?=?len?/?2?-?1;?//last?node's?root

????for?(?;?i?>=?0;?i--)
????{
????????heapify(arr,?len,?i);
????}
}
void?SortHeap(ElemType?arr[],?int?len)
{
????int?i?=?len?-?1;

????for?(?;?i?>?0;?i--)
????{
????????swap(&arr[0],?&arr[i]);
????????heapify(arr,?i,?0);?//調(diào)整堆屬性
????}
}

BOOL?isLeaf(int?root,?int?len)
{
????return?LeftChild(root)?<=?len?-?1???FALSE?:?TRUE;
}


偶比較懶，想了一會(huì)，弄了一個(gè)自動(dòng)化測(cè)試的代碼：

#include?"heap.h"

#define?SIZE?5
#define?TEST_TIMES?100

int?main(void)
{
????int?i?=?0;
????ElemType?arr[SIZE];

????for?(?;?i?<?TEST_TIMES;?i++)
????{
????????RandArray(arr,?ARRAY_LENGTH(arr),?20);

????????MakeHeap(arr,?ARRAY_LENGTH(arr));
????????SortHeap(arr,?ARRAY_LENGTH(arr));
????????check_ascending(arr,?ARRAY_LENGTH(arr));
????????PrintArray(arr,?ARRAY_LENGTH(arr),?"%d?");
????}

????return?EXIT_SUCCESS;
}