堆的构建与堆排序

堆是一种常用数据结构，我们在编写算法的时候，会常用他，为了理解这种数据结构，我自己学着实现了一下，几个基本操作，返回父节点的位置，左儿子节点的位置，右儿子节点的位置，调整堆，该方法是堆中最重要的操作方法！建立堆，堆排序都是以这个操作方法为核心的，重点说明下这个方法:

输入为数组A[],位置i，

1。先获取他的两个儿子的位置，

2. 判断儿子和父亲谁大，

3.若儿子比父亲大，则交换儿子和父亲的位置！

4.并继续递归调整被交换过儿子的位置！

[cpp] class MyHeap
{
public:
MyHeap();
~MyHeap();
int Parent(int i);
int Left(int i);
int Right(int i);

void Max_HeapPIFy(int A[],int i);

int exchange(int A[],int i,int largest);


int size;

int BuildMaxHeap(int A[],int n);

void HeapSort(int A[],int n);
private:

};

MyHeap::MyHeap()
{

}

MyHeap::~MyHeap()
{

}

int MyHeap::Parent(int i)
{
return i/2;
}

int MyHeap::Left(int i)
{
return 2*(i+1)-1;
}

int MyHeap::Right(int i)
{
return 2*(i+1);
}

void MyHeap::Max_HeapPIFy(int A[],int i)
{
int l = Left(i);
int r = Right(i);

int largest ;

if (lA[i])
{
largest = l;
}
else
{
largest = i;
}
if (rA[largest])
{
largest = r;
}

if (largest!=i)
{
exchange(A,i,largest);
Max_HeapPIFy(A,largest);
}

}

int MyHeap::exchange(int A[],int i,int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
return 0;
}

int MyHeap::BuildMaxHeap(int A[],int n)
{
size = n;

for (int i = (n)/2; i>=0; i--)
{
Max_HeapPIFy(A,i);
}
return 0;
}

void MyHeap::HeapSort(int A[],int n)
{
BuildMaxHeap(A,n);

for (int i = size-1; i>0; i--)
{
exchange(A,0,i);
size -=1;
Max_HeapPIFy(A,0);
}

}

class MyHeap
{
public:
MyHeap();
~MyHeap();
int Parent(int i);
int Left(int i);
int Right(int i);

void Max_HeapPIFy(int A[],int i);

int exchange(int A[],int i,int largest);

int size;

int BuildMaxHeap(int A[],int n);

void HeapSort(int A[],int n);
private:

};

MyHeap::MyHeap()
{

}

MyHeap::~MyHeap()
{

}

int MyHeap::Parent(int i)
{
return i/2;
}

int MyHeap::Left(int i)
{
return 2*(i+1)-1;
}

int MyHeap::Right(int i)
{
return 2*(i+1);
}

void MyHeap::Max_HeapPIFy(int A[],int i)
{
int l = Left(i);
int r = Right(i);

int largest ;

if (lA[i])
{
largest = l;
}
else
{
largest = i;
}
if (rA[largest])
{
largest = r;
}

if (largest!=i)
{
exchange(A,i,largest);
Max_HeapPIFy(A,largest);
}

}

int MyHeap::exchange(int A[],int i,int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
return 0;
}

int MyHeap::BuildMaxHeap(int A[],int n)
{
size = n;

for (int i = (n)/2; i>=0; i--)
{
Max_HeapPIFy(A,i);
}
return 0;
}

void MyHeap::HeapSort(int A[],int n)
{
BuildMaxHeap(A,n);

for (int i = size-1; i>0; i--)
{
exchange(A,0,i);
size -=1;
Max_HeapPIFy(A,0);
}

}

[cpp] int A[10]={2,3,4,5,6,7,8,9,0,1};

MyHeap m_heap;

m_heap.BuildMaxHeap(A,10);
for (int i = 0; i <10; i++)
{
cout< }
cout < m_heap.HeapSort(A,10);

for (int i = 0; i <10; i++)
{
cout< }
cout <

int A[10]={2,3,4,5,6,7,8,9,0,1};

MyHeap m_heap;

m_heap.BuildMaxHeap(A,10);
for (int i = 0; i <10; i++)
{
cout< }
cout < m_heap.HeapSort(A,10);

for (int i = 0; i <10; i++)
{
cout< }
cout <