一:什么是堆?
1.堆: n个元素的序列{k1,k2,k3,.....kn}当且仅当满足以下关系是,称为堆. {ki <= k2i 且 ki <= k2i+1} 或
{k2i <= ki 且 k2i+1 <= ki} (i = 1,2,...[n/2] ).这也是堆的一个性质.

2.堆结构是一种数组对象堆,它可以被视为一棵完全二叉树如下图,  书中每个节点与数组中存放该节点中值的那个元素
对应,除了最后一层,其余的每个节点都是满的.因为堆可看成是一棵完全二叉树,那它就满足一些树的性质,
对于有n个结点的完全二叉树,对任一结点i 有:  
  1)如果 i = 1,则结点i是二叉树的根,无双亲;
    2)如果i > 1,则其双亲Parent(i)是[ i / 2];
    3)如果2i > n,则结点i 无左孩子(结点i为叶子结点);否则,其左孩子Lift_child(i) 是结点2i.
    4)如果2i + 1 > n,则结点i无右孩子;否则,其右孩子right_child(i)是结点2i + 1.
    5)其非终端结点是第[ n / 2]个元素,(非终端结点是指:完全二叉树中的最后一个带有叶子的结点).
            

二:堆的分类
堆包含: 1.大根堆. 2.小根堆.      
        1. 大根堆必须满足: {ki <= k2i , ki <= k2i+1}  (i = 1,2,...[n/2] ), 大根堆排序后元素是由小到大的顺序.
        2.小根堆必须满足:  {k2i <= ki , k2i+1 <= ki} (i = 1,2,...[n/2] ).  小根堆排序后元素是由大到小的顺序.
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，
故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示:



在下面所举的例子或代码中默认的是数组中元素是从下标1开始存储的.

三:如何实现堆排序?
1.堆排序需要解决的两个问题就是:(1)如何由一个无序序列建成一个堆? (2)如何在输出堆顶元素之后,
   调整剩余元素成为一个新的堆?
      
2. 让一个无序序列建成一个堆的最重要的步骤就是堆调整(牢记堆性质).
    堆调整的思想:
       1).把待调整的记录当成根,然后 比较此根和其左,右孩子这三个数的大小,如果左,右孩子中还中有一个最大的,
            则把此最大值与根值交换(这是大根堆调整法,小根堆调整只需找到最小的值并与根交换就行),
       2).接着从最大值下标开始,并又以此结点为根重复1)中的步骤直到最大值下标循环的叶子结点.
        3)如果1)中比较后得到的最大值(/最小值)仍为根,则表示以此根结点的子序列已满足堆性质,就已经是堆了,

下面就堆调整的伪代码:
    array[]可知是我们将要调整的序列数组,index 则表示的是将要调整的记录的下标.wait_adjust_length是待调整堆的长度.  

点击(此处)折叠或打开

• heap_adjust(NumType array[], int index ,int wait_adust_length)
  
•     lift_index = 2 * index ;//记录待调整记录的左孩子的下标
•     right_index = 2 * index + 1;//记录待调整记录的右孩子的下标
•   if lift_index <= wait_adjust_lenght and array[lift_index] > array[right_index]
•           then max_num_index = lift_index;
•           else max_num_index = right_index;
•   if right_index <= wait_adjust_length and array[right_index] > array[max_num_index]
•    then max_num_index = right_index;
•    if max_num_index != index
•         then exchange array[index] <---> array[max_num_index]
•           heap_adjust(array, max_num_index);
  

heap_adjust的作用过程如下图:  此处wait_adjust_length = 10;
        图a) 改堆的初始构造,在节点i =2处array[2]违反了堆的性质,因为它不大于它的两个子女(此处是以 大根堆 举例).  
在图b)中通过交换array[2]与array[4],因此在结点2处恢复的堆的性质,但又在结点4处违反了堆的性质现在递归调用heap_adjust(array, 4)就置index=4.
图(c)中在交换了array[4]与array[9]后,结点,结点4处堆性质得到恢复,递归调用heap_adjust(array, 9)对该数据结构不再引起任何变化.        
    在算法的每一步里,从元素array,array[lift_index]和array[right_index]中找到最大的,并将其下标存在max_num_index中.如果array[index]是最大的,则以index为根的子树已是堆,算法结束.否则,
index的某个子结点中有最大元素，则换array[index]和array[max_num_index]，从而使i及其子女
满足堆的性质，交换后的结点max_num_index中原先的array[index]，以该结点为根的子树又有可能
违反堆性质，因而，要对该子树递归调用heap_adjust.

一:什么是堆?
1.堆: n个元素的序列{k1,k2,k3,.....kn}当且仅当满足以下关系是,称为堆. {ki <= k2i 且 ki <= k2i+1} 或
{k2i <= ki 且 k2i+1 <= ki} (i = 1,2,...[n/2] ).这也是堆的一个性质.

2.堆结构是一种数组对象堆,它可以被视为一棵完全二叉树如下图,  书中每个节点与数组中存放该节点中值的那个元素
对应,除了最后一层,其余的每个节点都是满的.因为堆可看成是一棵完全二叉树,那它就满足一些树的性质,
对于有n个结点的完全二叉树,对任一结点i 有:  
  1)如果 i = 1,则结点i是二叉树的根,无双亲;
    2)如果i > 1,则其双亲Parent(i)是[ i / 2];
    3)如果2i > n,则结点i 无左孩子(结点i为叶子结点);否则,其左孩子Lift_child(i) 是结点2i.
    4)如果2i + 1 > n,则结点i无右孩子;否则,其右孩子right_child(i)是结点2i + 1.
    5)其非终端结点是第[ n / 2]个元素,(非终端结点是指:完全二叉树中的最后一个带有叶子的结点).
            

二:堆的分类
堆包含: 1.大根堆. 2.小根堆.      
        1. 大根堆必须满足: {ki <= k2i , ki <= k2i+1}  (i = 1,2,...[n/2] ), 大根堆排序后元素是由小到大的顺序.
        2.小根堆必须满足:  {k2i <= ki , k2i+1 <= ki} (i = 1,2,...[n/2] ).  小根堆排序后元素是由大到小的顺序.
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，
故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示:



在下面所举的例子或代码中默认的是数组中元素是从下标1开始存储的.

三:如何实现堆排序?
1.堆排序需要解决的两个问题就是:(1)如何由一个无序序列建成一个堆? (2)如何在输出堆顶元素之后,
   调整剩余元素成为一个新的堆?
      
2. 让一个无序序列建成一个堆的最重要的步骤就是堆调整(牢记堆性质).
    堆调整的思想:
       1).把待调整的记录当成根,然后 比较此根和其左,右孩子这三个数的大小,如果左,右孩子中还中有一个最大的,
            则把此最大值与根值交换(这是大根堆调整法,小根堆调整只需找到最小的值并与根交换就行),
       2).接着从最大值下标开始,并又以此结点为根重复1)中的步骤直到最大值下标循环的叶子结点.
        3)如果1)中比较后得到的最大值(/最小值)仍为根,则表示以此根结点的子序列已满足堆性质,就已经是堆了,

下面就堆调整的伪代码:
    array[]可知是我们将要调整的序列数组,index 则表示的是将要调整的记录的下标.wait_adjust_length是待调整堆的长度.  

点击(此处)折叠或打开

• heap_adjust(NumType array[], int index ,int wait_adust_length)
  
•     lift_index = 2 * index ;//记录待调整记录的左孩子的下标
•     right_index = 2 * index + 1;//记录待调整记录的右孩子的下标
•   if lift_index <= wait_adjust_lenght and array[lift_index] > array[right_index]
•           then max_num_index = lift_index;
•           else max_num_index = right_index;
•   if right_index <= wait_adjust_length and array[right_index] > array[max_num_index]
•    then max_num_index = right_index;
•    if max_num_index != index
•         then exchange array[index] <---> array[max_num_index]
•           heap_adjust(array, max_num_index);
  

heap_adjust的作用过程如下图:  此处wait_adjust_length = 10;
        图a) 改堆的初始构造,在节点i =2处array[2]违反了堆的性质,因为它不大于它的两个子女(此处是以 大根堆 举例).  
在图b)中通过交换array[2]与array[4],因此在结点2处恢复的堆的性质,但又在结点4处违反了堆的性质现在递归调用heap_adjust(array, 4)就置index=4.
图(c)中在交换了array[4]与array[9]后,结点,结点4处堆性质得到恢复,递归调用heap_adjust(array, 9)对该数据结构不再引起任何变化.        
    在算法的每一步里,从元素array,array[lift_index]和array[right_index]中找到最大的,并将其下标存在max_num_index中.如果array[index]是最大的,则以index为根的子树已是堆,算法结束.否则,
index的某个子结点中有最大元素，则换array[index]和array[max_num_index]，从而使i及其子女
满足堆的性质，交换后的结点max_num_index中原先的array[index]，以该结点为根的子树又有可能
违反堆性质，因而，要对该子树递归调用heap_adjust.