// Max_Heapify.cpp : Defines the entry point for the console application.//堆排序是一种原地排序，如果试图引入数组，那么将失去这一优势。//最大堆满足条件A[Parent[i]]>=A[i]
#include "stdafx.h"#include <iostream>#include <algorithm>
class Max_Heapify{
private: int m_size;
int Parent(int i){ return i/2; }
int Left(int i) { return 2*i; } int Right(int i) {return 2*i+1;} void Max_Adus_Heapify(int A[],int i) { int l = Left(i); int r = Right(i); int largest = i; if((l <= m_size) && (A[l] > A[i]))// largest = l;//从元素A[Left(i)],A[Right(i)],A[i]找出最大的元素。 if((r <= m_size) && (A[r] >A[largest])) largest = r;//并将下标存放在largest中。如果A[i]最大，则以i为根的子树而使i及其子树满足堆的性质。 if (largest != i)//如果A[i]是最大的，则以i为根的子树已是最大根，程序结束。 { std::swap(A[i], A[largest] );// Max_Adus_Heapify(A, largest); //
}//下标为largest的节点在交换后的值是A[i]，以该节点为根的子树又有可能违反最大堆的性质。因而要递归调用。 } void Build_Max_Heapify(int A[]) { for(int i = m_size/2; i >= 0; i--) Max_Adus_Heapify(A, i); }//建堆：子数组A[n/2+1...n]中的元素都是叶子节点，因此每个都可以看作只含一个元素的堆.//m_size/2与m_size一样都正确，也就是上面句子的解释。public: Max_Heapify():m_size(NULL){} Max_Heapify(int A[],int size) { m_size = size-1; Build_Max_Heapify(A); } void Heap_Sort(int A[]) { Build_Max_Heapify(A); for(int i = m_size; i >= 1; i--) { std::swap(A[0], A[i]); --m_size; Max_Adus_Heapify(A, 0); } } //Build_Max_Heapify(),将使A[0]达到最大值。这样一直循环交换存放在数组A[i]中，递归调用。 ~Max_Heapify(){}
};int main(int argc, char* argv[]){ int A[11] = { 30, 45, 22, 72, 9, 12, 26, 80, 22, 43,1}; int size = sizeof(A)/sizeof(A[0]); Max_Heapify p(A, size); p.Heap_Sort(A); std::copy(A, A+11, std::ostream_iterator<int>(std::cout, " ")); return 0;}