(중요!!!) 연산자 오버로딩 및 Heap 직접 구현

내가 만든 구조체에 대한

"연산자"를 정의하여 사용하는 것이다.

 

priority_queue에서

a.operator<(b) 가 참일 때

b를 heap의 top에 올려준다

 

// 최소 힙
bool operator < (const T &a, const T &b)
{
    return a.d > b.d;
}

 

b의 d가 작을 때,

즉 return 값이 true 일 때

b를 heap의 top에 올려준다 -> 최소 힙

 

<최대 힙>

return a < b;

 

<최소 힙>

return a > b;

 

 

구조체 비교 연산에서는 위와 동일

sort에서는 반대이다.

 

 

<Partial sort>

 

MAX 10만명의 User에 대해 수입이 주어진다.
수입이 가장 큰 user 10명의 uID를 수입에 대해 내림차순으로 구하라.

 

void addUser (int uID, int income)

user을 추가하는 함수이다.

Parameters:

uID: user id, 0부터 시작해서 순차적으로 증가한다 (0 ≤ uID < 100000)

income: user의 수입, 클수록 우선순위가 높다. 만약 수입이 동일한 경우 uID가 작은 user의 우선순위가 높다.

 

int getTop10 (int result[MAX_CANDI])

수입이 가장 큰 user 10명의 uID를 수입에 대해 내림차순으로 구하는 함수이다.

총 user의 수가 10명이 되지 않으면 존재하는 user의 uID를 수입에 대해 내림차순으로 구한다.

result의 개수를 반환한다.

Parameters:

result[]: 수입이 큰 순서대로 10개의 uID를 저장한다. (1 ≤ result 개수 ≤ 10)

 

<소스 코드>

int genzai;
int user_cnt;
 
struct info {
    int income;
    int id;
};
 
// 수입 최대 힙
// id 최소 힙
bool operator < (const info& a, const info& b)
{
    if (a.income == b.income)
    {
        return a.id > b.id;
    }
    return a.income < b.income;
}
 
int arr[100004];
info Heap[100004];
 
void Heap_push(info data)
{
    int idx = ++genzai;
    Heap[idx] = data;
 
    while ((idx != 1) && (Heap[idx / 2] < data))
    {
        info tmp = Heap[idx];
        Heap[idx] = Heap[idx / 2];
        Heap[idx / 2] = tmp;
 
        idx = idx / 2;
    }
}
 
info Heap_pop()
{
    info result = Heap[1];
 
    Heap[1] = Heap[genzai];
    genzai--;
 
    // idx
    int parent = 1;
    int child;
 
    while (true)
    {
        child = parent * 2;
 
        // 자식노드 두 개 중 우선순위 높은 거 선택
        if (child + 1 <= genzai && Heap[child] < Heap[child + 1])
            child++;
 
        // 부모가 우선순위 높으면 break
        if (child > genzai || Heap[child] < Heap[parent])
            break;
 
        info tmp = Heap[child];
        Heap[child] = Heap[parent];
        Heap[parent] = tmp;
 
        parent = child;
    }
    return result;
}
 
void init()
{
    user_cnt = 0;
    genzai = 0;
}
 
void addUser(int uID, int height)
{
    Heap_push({ height, uID });
    user_cnt++;
}
 
// pop 10번 하고 다시 push 해서 넣어줘야함
int getTop10(int result[10])
{
    info tmp[10];
    int idx = 0;
    while (true)
    {
        tmp[idx] = Heap_pop();
        result[idx] = tmp[idx].id;
        idx++;
        if (idx == 10 || idx == user_cnt)
            break;
    }
 
    for (int i = 0; i < idx; i++)
    {
        Heap_push(tmp[i]);
    }
 
    return idx;
}

int user_cnt;
 
struct info {
    int income;
    int id;
};
 
// 수입 최대 힙
// id 최소 힙
bool operator < (const info& a, const info& b)
{
    if (a.income == b.income)
    {
        return a.id > b.id;
    }
    return a.income < b.income;
}
 
info Top10[11];
int ptr;
 
void swap(struct info* a, struct info* b)
{
    struct info tmp;
 
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void push(int id, int income)
{
    int idx = ptr;
    Top10[idx] = { income ,id };
    idx++;
 
    for (int i = idx - 2; i >= 0; i--)
    {
        if (Top10[i] < Top10[i + 1])
        {
            //swap(&Top10[i], &Top10[i + 1]);
            info tmp = Top10[i];
            Top10[i] = Top10[i + 1];
            Top10[i + 1] = tmp;
        }
    }
 
    if (idx > 10)
        idx = 10;
    ptr = idx;
}
 
void init()
{
    user_cnt = 0;
    ptr = 0;
}
 
void addUser(int uID, int height)
{
    push(uID, height);
    user_cnt++;
}
 
int getTop10(int result[10])
{
    for (int i = 0; i < ptr; i++)
        result[i] = Top10[i].id;
 
    return ptr;
}