堆排序彻底理解

//baike.baidu.com/view/157305.htm
    1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )

堆的定义：
    n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
    (1) ki≤K2i 且 ki≤K2i+1    (1≤i≤n) ---- 小根堆  
或者
    大根堆：(2) Ki≥K2i 且 ki≥K2i+1    (1≤i≤n)

    若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
    树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

 

堆排序算法特性：

    堆排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
    堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
    堆排序是就地排序，辅助空间为O(1)，
    它是不稳定的排序方法。

 

堆排序过程

有以下三个操作：

  1) 最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
  2) 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  3) 排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算

 

(1) 最大堆调整：

//blog.csdn.net/v_JULY_v/article/details/6198644 ===================

    为了保持最大堆的性质，我们运用MAX-HEAPIFY操作，作调整，递归调用此操作，使i为根的子树成为最大堆。

MAX-HEAPIFY算法，如下所示（核心）：

    MAX-HEAPIFY(A, i)
     1  l ← LEFT(i)
     2  r ← RIGHT(i)
     3  if l ≤ heap-size[A] and A[l] > A[i]
     4     then largest ← l
     5     else largest ← i
     6  if r ≤ heap-size[A] and A[r] > A[largest]
     7     then largest ← r
     8  if largest ≠ i
     9     then exchange A[i] <-> A[largest]
    10         MAX-HEAPIFY(A, largest)

    如上，首先第一步，在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个，将其下标存储在largest中。如果A[i]已经就是最大的元素，则程序直接结束。否则，i的某个子结点为最大的元素，将其，即A[largest]与A[i]交换，从而使i及其子女都能满足最大堆性质。下标largest所指的元素变成了A[i]的值，会违反最大堆性质，所以对largest所指元素调用MAX-HEAPIFY。如下，是此MAX-HEAPIFY的演示过程（下图是把4调整到最底层，一趟操作，但摸索的时间为LogN）：

   

 

    由上图，我们很容易看出，初始构造出一最大堆之后，在元素A[i]，即16，大于它的俩个子结点4、10，满足最大堆性质。所以，i下调指向着4,小于,左子14，所以，调用MAX-HEAPIFY，4与其子，14交换位置。但4处在了14原来的位置之后，4小于其右子8，又违反了最大堆的性质，所以再递归调用MAX-HEAPIFY，将4与8，交换位置。于是，满足了最大堆性质，程序结束。

 

时间复杂度：

    MAX-HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时，其运行时间为调整元素A[i]、A[LEFT(i)]，A[RIGHT(i)]的关系时所用时间为O(1)，再加上，对以i的某个子结点为根的子树调用MAX-HEAPIFY所需的时间，且i结点的子树大小至多为n/2 (原文为2n/3)，所以，MAX-HEAPIFY的运行时间为
     T (n) ≤ T(n/2) + Θ(1).

我们，可以证得此式子的递归解为T(n)=O(lgn)。具体证法，可参考算法导论第6章之6.2节，这里，略过。

 

(2) 建堆

    BUILD-MAX-HEAP(A)
    1  heap-size[A] ← length[A]
    2  for i ← |_length[A]/2_| downto 1
    3       do MAX-HEAPIFY(A, i)   

//建堆，怎么建列?原来就是不断的调用MAX-HEAPIFY(A, i)来建立最大堆。

 

(3) 排序及实现

//baike.baidu.com/view/157305.htm ================================

/*
   用大根堆排序的基本思想
   ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
   ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，
   由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
   ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
   然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
   由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，

      且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys，
   同样要将R[1..n-2]调整为堆。
   ……
   直到无序区只有一个元素为止。
*/

void HeapAdjust(int array[], int i, int nLen)
{
    int nChild;
    int nTemp;

    nTemp = array[i]； // 父结点。    swap-1
    for(; (2*i+1) < nLen; i = nChild)
    {       
        //子结点的位置 = 2 * (父结点的位置) + 1
        nChild = 2*i + 1;

        //取子结点中较大的
        if(nChild < nLen - 1 && array[nChild+1] > array[nChild])
            ++nChild;
        // 如果较大的子结点>父结点，那么把较大的往上移动，替换父结点
        if(nTemp < array[nChild])
        {
            array[i] = array[nChild];  // swap-2
        }
        else //否则父结点已经是最大的
            break;

        // 最后把被替换的父结点值放回子结点处
        array[nChild] = nTemp;  // swap-3
    }
}

void HeapSort(int array[], int length)
{
    int i, nTemp;
    //调整序列的前半部分，调整完之后第一个元素是序列的最大的元素
    //从而将array[0, lenght-1]建成大根堆
    for(i = length/2 - 1; i >= 0; --i)
    {
        HeapAdjust(array, i, length);
    }
    //从最后一个元素开始对序列进行调整

    for( i = length-1; i > 0; --i)
    {
        //把第一个元素和当前的最后一个元素交换
        //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        nTemp = array[0];
        array[0] = array[i];  array[i] = nTemp;
        //缩小范围，将array[0..i--]重新调整为大根堆
        HeapAdjust(array, i, length);
    }
}

 

//end