堆的構建與堆排序

堆是一種常用數據結構，我們在編寫算法的時候，會常用他，為了理解這種數據結構，我自己學著實現了一下，幾個基本操作，返回父節點的位置，左兒子節點的位置，右兒子節點的位置，調整堆，該方法是堆中最重要的操作方法！建立堆，堆排序都是以這個操作方法為核心的，重點說明下這個方法:

輸入為數組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 (l<size&&A[l]>A[i]) 
    { 
        largest = l; 
    } 
    else 
    { 
        largest = i; 
    } 
    if (r<size&&A[r]>A[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 (l<size&&A[l]>A[i])
 {
  largest = l;
 }
 else
 {
  largest = i;
 }
 if (r<size&&A[r]>A[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<<A[i]<<"\t"; 
    } 
    cout <<endl; 
    m_heap.HeapSort(A,10); 
     
    for (int i = 0; i <10; i++) 
    { 
        cout<<A[i]<<"\t"; 
    } 
    cout <<endl; 

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<<A[i]<<"\t";
 }
 cout <<endl;
 m_heap.HeapSort(A,10);
 
 for (int i = 0; i <10; i++)
 {
  cout<<A[i]<<"\t";
 }
 cout <<endl;