スタックソートで配列内の最大K個数を探す

/***********************************************************************************
   （Heapsort）                     。
               ，          ：
              （    ）     。
              。       0     ：
   i         (2*i+1);
   i         (2*i+2);
   i        floor((i-1)/2);
    
        ，             。          ：
     （Min_Heapify）：           ，            
     （Build_Min_Heap）：          
 ：           。

            K  
    K          K  。            K         。
        X，  X     Y ，          。  X      ，
   X      Y，     ，X           ，            。
          O(logK)。          O(N*logK)。
              ，    。              ，
*************************************************************************************/

#include <cmath>
#include<cstdlib>
#include<time.h>
#include<cstdio>
#include<iostream>
using namespace std;
//      
void Random(int a[],int n)
{
    int i=0;
    srand( (unsigned)time( NULL ) );
    while(i<n)
    {
        a[i++]=rand()/999;
    }
}
void print(int a[], int len)
{
    int i;
    for (i = 0; i < len; i++)
    printf("%6d   ", a[i]);
    printf("
");
}


int parent(int);
int left(int);
int right(int);
void Min_Heapify(int [], int, int);
void Build_Min_Heap(int A[],int size);
void HeapSort(int [], int);

/*   */
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}

/*    */
int left(int i)
{
    return (2 * i + 1);
}

/*    */
int right(int i)
{
    return (2 * i + 2);
}

/*           */
void Min_Heapify(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int least;
    int temp;
    /*                   */
    if(l < heap_size && A[l] < A[i])
    {
        least = l;
    }
    else
    {
        least = i;
    }
    if(r < heap_size && A[r] < A[least])
    {
        least = r;
    }
    /*         ，               */
    if(least != i)
    {
        temp = A[i];
        A[i] = A[least];
        A[least] = temp;
        /*                ，      */
        Min_Heapify(A, least, heap_size);
    }
}

/*     */
void Build_Min_Heap(int A[],int size)
{
    /*     A[0]            2*i+1      2*i+2 */
    /*                     
    0 1 2 ->mid=1=3/2    n/2
    0 1 2 3 ->mid=2=4/2     n/2
    0 1 2 3 4 ->mid=2=5/2   n/2
    0 1 2 3 4 5 ->mid=3=6/2 n/2                       
    */
    int begin = size/2 ;  //     
    for(int i = begin; i >= 0; i--)
    {
        Min_Heapify(A, i, size);
    }
}


/*     */
void HeapSort(int A[], int heap_size)
{
    Build_Min_Heap(A,heap_size);
    //                      
    int temp;
    //a[0]          a[heap_size - 1]          
    /*                */
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        //                
        Min_Heapify(A, 0, i);  //i                   
    }
}

void TopK(int arr[],int n,int K)
{
    if(n<K)
    {
        cout<<"error"<<endl;
        return;
    }
    int *heap=new int[K];
    //    K           
    for(int i=0;i<K;i++)
    {
        heap[i]=arr[i];
    }
    Build_Min_Heap(heap,K);//     
    //                      (               )
    for(int i=K;i<n;i++)
    {
        if(arr[i]>heap[0])
        {
            heap[0]=arr[i];
            //                  
            Min_Heapify(heap,0,K);
        }
    }
    for(int i=0;i<K;i++)
        cout<<heap[i]<<' ';
    delete []heap;
}

int main()
{
    int a[30] = {0};
    Random(a,30);
    print(a,30);
    cout<<endl<<"------------------------------------"<<endl;
    TopK(a,30,5);
    cout<<endl<<"------------------------------------"<<endl;
    HeapSort(a,30);
    cout<<endl<<"-----------------------------------"<<endl;
    print(a,30);
    return 0;
}
/******************
     21        0        7       26       10       11       23       10        4
      1       23        3       10       25       31       31       17       28
      11       31       27       23       19        7       19       21       20
        6       18       14

------------------------------------
27 28 31 31 31
------------------------------------

-----------------------------------
    31       31       31       28       27       26       25       23       23
     23       21       21       20       19       19       18       17       14
      11       11       10       10       10        7        7        6        4
        3        1        0

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

*******************/