【正确答案】 A

【答案解析】 堆是一种特殊的树形数据结构，其每个结点都有一个值，通常提到的堆都是指一棵完全二叉树。
   堆排序是树形选择排序，在排序过程中，将R[1...N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
   堆一般分为大顶堆和小顶堆两种不同的类型。对于给定n个记录的序列(r(1)，r(2)，…，r(n))，当且仅当满足条件(r(i)＞=r(2i)且r(i)＞=r(2i+1))时称为大顶堆，此时，堆顶元素为最大值。对于给定n个记录的序列(r(1)，r(2)，…，r(n))，当且仅当满足条件(r(i)＜=r(2i)且r(i)＜=r(2i+1))时称为小顶堆，此时，堆顶元素必为最小值。
   以小顶堆为例：堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个小顶堆，将堆的最后一个元素与堆顶元素(即二叉树的根结点)进行交换后，堆的最后一个元素即为最小记录；接着将前(n-1)个元素(即不包括最小记录)重新调整为一个小顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最大记录，此时可得到一个有序序列。
   堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。
   建立小顶堆的方法为：从最后一个非叶子结点开始，找出这个结点、左孩子、右孩子的最小值与这个结点的值交换，由于交换可能会引起孩子结点不满足小顶堆的性质，所以，每次交换之后需要重新对被交换的孩子结点进行调整。对于题目所给的数组构建小顶堆的过程如图所示。