排序算法的详细介绍(五) -- 堆排序

常见排序算法归档介绍:

堆排序 Heap Sort

算法描述

堆排序是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束.
最大堆调整(Max-Heapify): 将堆的末端子节点作调整,使得子节点永远小于父节点.
创建最大堆(Build-Max-Heap): 将堆所有数据重新排序,使其成为最大堆.
堆排序(Heap-Sort): 移除位在第一个数据的根节点,并做最大堆调整的递归运算.

实例分析

先注意一个问题: 数组都是 Zero-Based ,这就意味着我们的堆数据结构模型要发生改变.

heap_and_array_zero_based

相应的，几个计算公式也要作出相应调整:
1. Parent(i) = floor((i-1)/2), i 的父节点下标,
2. Left(i) = 2i + 1, i 的左子节点下标,
3. Right(i) = 2(i + 1), i 的右子节点下标,
最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质, 是创建最大堆的核心子程序, 作用过程如图所示:

Max_heapify_Procedure

由于一次调整后,堆仍然违反堆性质,所以需要递归的测试,使得整个堆都满足堆性质,用 JavaScript 可以表示如下:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
  var iMax = index,
      iLeft = 2 * index + 1,
      iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
  }
  if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
  }
  if (iMax != index) {
    swap(array, iMax, index);
    maxHeapify(array, iMax, heapSize); // 递归调整
  }
}
function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

创建最大堆(Build-Max-Heap)的作用是将一个数组改造成一个最大堆,接受数组和堆大小两个参数,Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组,建立最大堆.
因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质,所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质.如果最大堆的数量元素是 n,那么 Build-Max-Heap 从 Parent(n) 开始,往上依次调用 Max-Heapify.流程如下:

building_a_heap

用 JavaScript 描述如下:

function buildMaxHeap(array, heapSize) {
  var i,
      iParent = Math.floor((heapSize - 1) / 2);
      
  for (i = iParent; i >= 0; i--) {
    maxHeapify(array, i, heapSize);
  }
}

堆排序(Heap-Sort)是堆排序的接口算法,Heap-Sort先调用Build-Max-Heap将数组改造为最大堆,然后将堆顶和堆底元素交换,之后将底部上升,最后重新调用Max-Heapify保持最大堆性质.由于堆顶元素必然是堆中最大的元素,所以一次操作之后,堆中存在的最大元素被分离出堆,重复n-1次之后,数组排列完毕.整个流程如下:

sort_a_heap

用 JavaScript 描述如下:

function heapSort(array, heapSize) {
  buildMaxHeap(array, heapSize);
  for (int i = heapSize - 1; i > 0; i--) {
    swap(array, 0, i);
    maxHeapify(array, 0, i);
  }  
}

代码实现

function heapSort(array) {
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  function maxHeapify(array, index, heapSize) {
    var iMax,
      iLeft,
      iRight;
    while (true) {
      iMax = index;
      iLeft = 2 * index + 1;
      iRight = 2 * (index + 1);
      if (iLeft < heapSize && array[index] < array[iLeft]) {
        iMax = iLeft;
      }
      if (iRight < heapSize && array[iMax] < array[iRight]) {
        iMax = iRight;
      }
      if (iMax != index) {
        swap(array, iMax, index);
        index = iMax;
      } else {
        break;
      }
    }
  }
  function buildMaxHeap(array) {
    var i,
      iParent = Math.floor(array.length / 2) - 1;
    for (i = iParent; i >= 0; i--) {
      maxHeapify(array, i, array.length);
    }
  }
  function sort(array) {
    buildMaxHeap(array);
    for (var i = array.length - 1; i > 0; i--) {
      swap(array, 0, i);
      maxHeapify(array, 0, i);
    }
    return array;
  }
  return sort(array);
}

此文参考于 bubkoo.com,十分感谢.
所有引用内容版权归原作者所有.
使用知识共享“署名-非商业性使用-相同方式共享 3.0 中国大陆”许可协议授权.

常见排序算法归档介绍:

堆排序 Heap Sort

算法描述

实例分析

代码实现

CATALOG

FEATURED TAGS