第四次：第一题

> 输入样例：
> ```c
Please input N and M : 10 5
Then, input them :
1 6 8 20 17 26 4 22 14 31
Initial max_heap :
31  26  20  17  22  6  4  1  14  8
Result heap :
31  26  22  20  17
>```

```c
#include <stdio.h>
#include "stdlib.h"
#include "malloc.h"

void HeapSort(int a[], int n);
void HeapAdjust(int a[], int m, int n);

int main(){
    // main function .
    int N, M, i, j, tmp,check;
    int * Monopoly;
    printf("Please input N and M : ");
    scanf("%d %d", &N, &M);
    Monopoly = (int *)malloc(sizeof(int) * N);
    printf("Then, input them : \n");
    for(i = 0; i < N; i++){
        j = i + 1;
        scanf("%d", &Monopoly[i]);
        while(j != 1){
            if(Monopoly[j - 1] > Monopoly[(j / 2) - 1]){
                tmp = Monopoly[j - 1];
                Monopoly[j - 1] = Monopoly[(j / 2) - 1];
                Monopoly[(j / 2) - 1] = tmp;
            }
            else{
                break;
            }
            j = j / 2;
        }
    }

// check the input max_heap
    printf("Initial max_heap :\n");
    for(check = 0; check < N; check++){
        printf("%d  ", Monopoly[check]);
    }
    printf("\n");

// heap_sort
    HeapSort(Monopoly, N);

// check the result
    printf("Result heap :\n");
    for(check = 1; check <= M; check++){
        printf("%d  ", Monopoly[N - check]);
    }

return 0;
}

void HeapAdjust(int a[], int m, int n){
	int i;
	int t = a[m];

for(i = 2 * m + 1;i <= n;i = 2 * i + 1){
		if(i < n && a[i + 1] > a[i])
			++i;
		if(t >= a[i])
			break;
		a[m] = a[i];
		m = i;
	}
	a[m] = t;
}

void HeapSort(int a[], int n){
	int i;
	int t;

for(i = n - 1;i > 0;i--){
		t = a[i];
		a[i] = a[0];
		a[0] = t;
		HeapAdjust(a, 0, i - 1);
	}
}
```