堆排序-c++

堆排序应该不会考笔试，但是知道它总是好的。

首先，堆排序会涉及到最大堆，最小堆。而这两种数据结构的基础都是完全二叉树。完全二叉树是一种特殊的二叉树。它的特殊性在于，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。 最大堆和对应的存储结构 从图中可以看出父节点和子节点的对应关系。相应的，几个计算公式：

• Parent(i) = floor((i-1)/2)，i 的父节点下标
  Left(i) = 2i + 1，i 的左子节点下标
  Right(i) = 2(i + 1)，i 的右子节点下标

对于堆排序，要两个关键步骤：

• 最开始最大堆的构建(Build-Max-Heap)
• 最大堆的调整（Max_heapify）

Max_heapify

最大堆调整过程

这里最巧妙的是引入了一个imax这个变量。这个是指示最后最大元素所在位置，然后将堆顶的元素和这个元素进行交换。然后继续调整交换以后的子树。

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;
}

回到堆排序，我们要做的是，先建立一个最大堆，然后将堆顶元素和最后一个元素交换 ，接着调整除最后一个元素的满二叉树为最大堆。其中第一步调整最大堆伪代码：

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

那么，堆排序的整个过程如下图： 堆排序示意图

伪代码：

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