【正确答案】(1)数据结构
   typedef int KeyType;
   typedef int DataType;
   typedef struct{
     KeyType key;    /*排序码字段*/
     DataType info;    /*记录的其他字段*/
   }RecordNode;
   typedef struct{
     int n;    /*n为文件中的记录个数*/
     RecordNode  *record;
   }SortObject;
   (2)思路
   堆之中，下标为i(i＞0)的结点的父结点的下标为(i-1)/2(取下整)。
   设序列*pvector中，除最后一条记录外已是一个堆。算法adjusttoHeap将该序列(包括最后一条记录)调整为堆。算法大体步骤是：先将当前位置置为最后一条记录，每当当前位置记录的关键码大于其父结点记录的关键码，就将两个记录交换位置，并将当前位置置为其父结点位置。
   根据此思想，算法createHeap是从空堆开始一个个添入元素并建堆的算法。每添入一个元素，就调用一次算法adjusttoHeap将序列调整为堆。
   (3)算法
   void adjusttoHeap(SortObject*pvector){
   /*序列*pvector中,除最后一条记录外已是一个堆。算法将该序列(包括最后一条记录)调整为堆*/
   int i=pvector-＞n-1;
   RecordNode temp=pvector-＞record[i];
   while(i＞0&&temp.key＞pvector-＞record[(i-1)/2].key){
       pvector-＞record[i]=pvector-＞record[(i-1)/2];
       i=(i-1)/2:
       }
       pvector-＞record[i]=temp;
   }
   (4)代价分析
   算法中有一个循环，循环次数不超过堆的高度，为O(log₂n)，因此该算法的时间代价为O(log₂n)。
   (5)从空堆开始的建堆算法
   SortObject*createHeap(KeyType*keys,int n){
   /*从空堆开始,依次添入n条记录(关键码保存在数组keys中),并建堆*/
   SortObject*pvector;
   int i;
   RecordNode temp;
   pvector=(SortObject。)malloc(sizeof(SortObject));
   pvector-＞n=0:
   for(i=0;i＜n;i++){
       temp.key=keys[i];
       pvector-＞record[pvector-＞n++]=temp;    /*添入一条记录*/
       adjusttoHeap(pvector);    /*调整为堆*/
     }
     return pvector;
   }
   (6)代价分析
   该算法中，主要的时间用在调用算法adjusttoHeap(调整为堆)上。一共调用n次，而算法adjusttoHeap的时间代价为O(log₂n)。故该算法的时间代价为O(nlog₂n)。