秋刀鱼在做梦

这个屌丝很懒，什么也没留下！

热门标签

最大堆排序Max_Heapify_max-heapify

作者：秋刀鱼在做梦 | 2024-08-07 17:55:06

踩

max-heapify

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

}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/943802