Algorithm之排序之堆排序（Heap Sort）

Algorithm之排序之堆排序（Heap Sort）

一、什么是堆

在讲述堆之前，首先看一下二叉树。

二叉树：
每个节点最多有两个子节点，且这两个子节点有左右次序之分。


1、满二叉树
二叉树的所有非叶子节点都被填满。
因此：一颗深度为 K 的满二叉树，其节点总数为：2的k次方 - 1

= 1 + 2 + 4 + 8 + ... + 2 pow(k-1)

= 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k-1 = 2pow(k) - 1

图（深度为 3 的满二叉树）：



2、完全二叉树
有 n 个节点，深度为 k 的二叉树，
当且仅当，这 n 个节点的排列序号，与深度为 k 的满二叉树中
序号为 1 至 n 的节点一一对应时，称之为完全二叉树。

即：
      - 除了最外层，其它层都是有序且填满的。
      - 上一层没有排完，不能排下一层。


图（深度为 3 的完全二叉树）：



3、堆
仅从数据结构角度看：符合完全二叉树的数据结构称之为：堆。
且，所有父节点比其下子节点都大（或小），
但，堆不要求每层中左右子节点的大小顺序。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。



二、堆的操作方法

问题背景：为什么要操作堆？
从数据结构可以看出，堆是用来排序的。
所以对堆的操作，基本上都是排序操作。

1、排序之：插入节点
每次插入都是将新数据放在数组最后。然后依次向上调整。
直至符合：父节点比子节点都大（或小）。

2、排序之：删除节点
按定义，堆中每次都只能删除最顶层的那个节点（数组中索引为0的元素）。
为了便于重建堆，实际的操作是：
1. 将数组最末尾的元素与根节点位置调换，
2. 然后删除最末尾节点。
3. 然后再只需调整根节点使其符合堆特性即可。（其它节点是已调整好的）


以最小堆为例：
调整根节点时先在左右子结点中找最小的，如果根结点比这个最小的子结点还小说明不需要调整了，
反之将父结点和它交换后，还需要再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。


三、堆与数组的关系
基于：数组的索引是从 0 开始（Zero-Based）：


从上图中可以发现，以数组表示的堆，其数据结构中的每个节点的索引值存在这样的特点：

    父节点：parent(i) = (i - 1) >> 1;

    子节点（左）：leftChild(i) = i * 2 + 1;

    子节点（右）：rightChild(i) = i * 2 + 2;


任何一个数组，附以上述规则，那么这个数组就可以被看作是一个堆。
也就是说，堆可以用数组表示。反之：任何一个数组，都可以逻辑为一个堆。

堆的逻辑结构：完全二叉树
堆的存储结构：数组（内存中一块地址连续的空间），或：一堆空间。

既于，数组具天然有序索引这一特性：数组的索引就是一个排好序的堆。
那么，只需要按照数组的索引将其值放置为符合堆的规则即可——堆排序。


四、堆排序的过程

堆排序共分两步：

第一步：将数组堆化

把数组的每个节点，调整为具有堆的该特性：所有的父节点都比子节点大（或小）。

方法：遍历数组的每个节点

1、遍历的方向：从最外层向内层遍历（自底向上）

2、从哪里开始：从后向前数，从第一个非叶子节点开始遍历。
（没有必要从叶子节点开始。
    叶子节点可以看作是已符合堆特点的节点。
    因为它没有子节点，所以作为父节点，它就是最大的。）
   
    第一个非叶子节点的索引值可以根据最后一个元素的索引值求得：
    lastNodeIndex = (lastLeafIndex - 1) >> 1 = (arr.length - 2) >> 1;

3、每步遍历的规则：
   非叶子节点与其下面的子节点做比较，大的排上面。

（虽然堆的子节点是不要求有大小顺序的，但是因为我们要对堆进行排序，
    故：对于每个节点和它的子节点都要相互比较大小。

   对于大堆，最大的那个排在父节点的位置。
   对于小堆，最小的那个排在父节点的位置。）
  
4、每步遍历多少次：如果子节点与父节点交换了位置，则交换位置后的父节点仍需要向下验证。








第二步：将堆化数组排序

堆排序的过程就是，不断移出最顶层（数组的第一个）元素的过程。
1、把移出的顶层元素与数组最后一个元素交换位置。
2、同时遍历的长度减 1，
3、然后从新调整剩余的数据，使其符合堆的特性。（
此时只需要调整最顶层元素即可，其它层都是已经被初始化好的）

重复该过程，直至需要遍历的数组长度为 0 。







排好序的堆就是一颗完全二叉树了：
1、所有的父节点都比子节点小（或大）
2、同一节点的左子节点比右子节点小（或大）




排序动画：



Javascript代码实现：

function heapSort(arr){
    
    // step 1. heapify array
    var len = arr.length - 1;
    var lastNodeIndex = (len - 1) >> 1;
    for(var i = lastNodeIndex; i >= 0; i--){
        maxHeapify(arr, i, len);
    }
          
    // step 2. reduce heap
    for(var i = 0; i < len; i++){
        swap(arr, 0, len - i);
        maxHeapify(arr, 0, len - i - 1);
    }
    
    return arr;
}

function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}



function maxHeapify(arr, index, len){
    var li = (index << 1) + 1,    // left child index.
        ri = li + 1,              // right child index.
        cMax = li;                // default Child Max valule.
        
    if(li > len) return;               // left child is out of range.             
    if(ri <= len && arr[ri] > arr[li]) // choose the bigger one.
        cMax = ri;            
    if(arr[cMax] > arr[index]){        // if
        swap(arr, index, cMax);        // swapped, 
        maxHeapify(arr, cMax, len);    // next check should be executed.
    }
}

/*

// alternative method for maxHeapify();
function maxHeapify2(array, index, len) {
    var iLeft, iRight, iMax;        
    while (true) {
      iLeft = (index << 1) + 1;
      iRight = iLeft + 1;
      iMax = iLeft;
      
      if(iLeft > len) break;
      if(iRight <= len && array[iRight] > array[iLeft])
          iMax = iRight;
      if(array[iMax] <= array[index]) break;
      swap(array, iMax, index);
      index = iMax;
    }
}

*/

测试：

var arr = [1,23,14,8,10,9,235,21,45,56,4,32,79,15,56,985,343];

heapSort(arr);

// [1, 4, 8, 9, 10, 14, 15, 21, 23, 32, 45, 56, 56, 79, 235, 343, 985]

Java 版本：

import java.util.Arrays;

public class HeapSort {
    private int[] arr;
    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort() {
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int lastLeafIndex = arr.length - 1;
        int beginIndex = (lastLeafIndex - 1) >> 1;
        for (int i = beginIndex; i >= 0; i--)
            maxHeapify(i, lastLeafIndex);
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = lastLeafIndex; i > 0; i--) {
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int parentNodeIndex, int lastLeafIndex) {
        int li = (parentNodeIndex << 1) + 1, // 左子节点索引
            ri = li + 1,                     // 右子节点索引
            cMax = li;                       // 子节点值最大索引，默认左子节点。
        
        if (li > lastLeafIndex) return;      // 左子节点索引超出计算范围，直接返回。
        if (ri <= lastLeafIndex && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if (arr[cMax] > arr[parentNodeIndex]) {
            swap(cMax, parentNodeIndex);      // 如果父节点被子节点调换，
            maxHeapify(cMax, lastLeafIndex);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

    /**
     * 测试用例
     *
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[] {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }
}

五、堆排序分析


堆排序与归并排序一样，是一种时间复杂度为O(N * logN)的算法，
同时和插入排序一样，是一种就地排序算法(不需要额外的存储空间)。









-
转载请注明，
原文出处：http://lixh1986.iteye.com/blog/2354246





-
引用：

堆_(数据结构)
https://zh.wikipedia.org/wiki/堆_(数据结构)

常见排序算法 - 堆排序 (Heap Sort)
http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

堆排序详解
http://blog.csdn.net/daiyudong2020/article/details/52529791

堆排序详解
http://www.cnblogs.com/hdk1993/p/4635923.html

堆排序 - 维基百科
https://zh.wikipedia.org/wiki/堆排序