【堆排 && 思路】資料結構實驗之排序四：尋找大富翁

一個看似很水但很坑的題：資料結構實驗之排序四：尋找大富翁

這題時間壓的很短隻有200ms，用平常的堆排序。直接T，别問我怎麼知道（心累啊），要不也不會寫這篇部落格。直接上代碼。這題關鍵在于用了一個很巧妙的思想，沒有去對所有1e6的資料全部堆排，而轉去維護了m個小頂堆，這樣效率大大提高。最終能維護成一個m個最大元素組成的小頂堆。最終輸出就好了。（*注：記得維護的是小頂堆而輸出要從大到小。是以還要進行一個簡單的排序。）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100005
long long int a[N];
int size;

void Insert(long long int m)
{
    a[++size] = m;
    int i;
    for(i = size; i != 0; i /= 2)
    {
        if(a[i] < a[i/2])
        {
            long long int t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else
            break;
    }
}

void Adjustment()
{
    int i, x;
    for(i = 1; 2 * i <= size; i = x)
    {
        if(2 * i + 1 <= size && a[i * 2] > a[i * 2 + 1])
            x = i * 2 + 1;
        else
            x = i * 2;
        if(a[i] > a[x])
        {
            long long int t = a[i];
            a[i] = a[x];
            a[x] = t;
        }
        else
            break;
    }
}

int main()
{
    int n, i, m;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)//建立小頂堆
    {
        int x;
        scanf("%d", &x);
        Insert(x);
    }
    for(i = m;i < n; i++)//維護小頂堆
    {
        int x;
        scanf("%d", &x);
        if(x > a[1])
        {
            a[1] = x;
            Adjustment();
        }
    }
    for(i = m;i > 0; i--)//再做一個排序
    {
        int t = a[1];
        a[1] = a[i];
        a[i] = t;
        size--;
        Adjustment();
    }
    for(i = 1;i <= m; i++)
    {
        if(i == m)
            printf("%lld\n", a[i]);
        else
            printf("%lld ", a[i]);
    }
    return 0;
}