더미 정렬 이해 전체 코드

/*
<   http://www.wutianqi.com/?p=1820 >


    

* Note:      (Heap Sort)
*/
#include <iostream>
using namespace std;

//           
void PrintArray(int data[], int size)
{
    for (int i=1; i<=size; ++i)
        cout <<data[i]<<"  ";
    cout<<endl;
}

//   ，      
// MaxHeapify a[i]     "  "，
//   i          
void MaxHeapify(int *a, int i, int size)
{
    int lt = 2*i, rt = 2*i+1;
    int largest;
    if(lt <= size && a[lt] > a[i])   //            
        largest = lt;
    else
        largest = i;
    if(rt <= size && a[rt] > a[largest])
        largest = rt;
    if(largest != i)
    {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        MaxHeapify(a, largest, size);
    }
}

//   
//        MaxHeapify      a[1..size]       
//
void BuildMaxHeap(int *a, int size)
{
    for(int i=size/2; i>=1; --i)
        MaxHeapify(a, i, size);
}

//    
//     BuildMaxHeap a[1..size]     
//          a[1]，      a[1] a[size]        
//                 ，    MaxHeapify  ，
//  a[1..size-1]     ，a[1]  a[1..size-1]      ，
//  a[1] a[size-1]        。
//     Heapify，            。
//   ：         a[1]           ，                 。
//              BuildMaxHeap     size/2 1          ，        a[1]  。
void HeapSort(int *a, int size)
{
    BuildMaxHeap(a, size);
    PrintArray(a, size);
    int len = size;
    for(int i=size; i>=2; --i)
    {
        int temp = a[1];
        a[1] = a[i];
        a[i] = temp;
        len--;
        MaxHeapify(a, 1, len);
        cout << "    :";
        PrintArray(a, size);
    }

}

int main()
{
    int size;
    int arr[100];
    cout << "Input the num of elements:
";
    cin >> size;
    cout << "Input the elements:
";
    for(int i=1; i<=size; ++i)
        cin >> arr[i];
    cout << endl;
    HeapSort(arr, size);
    cout << "    :";
    PrintArray(arr, size);
}
/*
   
Input the num of elements:
10
Input the elements:
50 36 41 19 23 4 20 18 12 22

50  36  41  19  23  4  20  18  12  22
    :41  36  22  19  23  4  20  18  12  50
    :36  23  22  19  12  4  20  18  41  50
    :23  19  22  18  12  4  20  36  41  50
    :22  19  20  18  12  4  23  36  41  50
    :20  19  4  18  12  22  23  36  41  50
    :19  18  4  12  20  22  23  36  41  50
    :18  12  4  19  20  22  23  36  41  50
    :12  4  18  19  20  22  23  36  41  50
    :4  12  18  19  20  22  23  36  41  50
    :4  12  18  19  20  22  23  36  41  50

Process returned 0 (0x0)   execution time : 2.411 s
Press any key to continue.

*/
/*
   
Input the num of elements:
10
Input the elements:
50 36 41 19 23 4 20 18 12 22

4  12  20  18  22  41  50  36  19  23
    :12  18  20  19  22  41  50  36  23  4
    :18  19  20  23  22  41  50  36  12  4
    :19  22  20  23  36  41  50  18  12  4
    :20  22  41  23  36  50  19  18  12  4
    :22  23  41  50  36  20  19  18  12  4
    :23  36  41  50  22  20  19  18  12  4
    :36  50  41  23  22  20  19  18  12  4
    :41  50  36  23  22  20  19  18  12  4
    :50  41  36  23  22  20  19  18  12  4
    :50  41  36  23  22  20  19  18  12  4

Process returned 0 (0x0)   execution time : 2.795 s
Press any key to continue.

*/