# 堆排序-c++

2018-03-01 10:57:24来源:https://www.jianshu.com/p/984e47bf0323作者:爱秋刀鱼的猫人点击

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

Max_heapify

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