[백준][C++] 11279 최대 힙

11279. 최대 힙

11279번: 최대 힙

문제 풀이1

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

문제 풀이2(우선순위 큐 구현)

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

우선순위 큐를 사용하면 아주 쉬운 문제였지만, 뭔가 날로 먹는 느낌이 들어 우선순위 큐를 자료구조 시간에 배운대로 구현해보았다.

 

전체적인 힙은 vector로 구현했다.

• 부모의 인덱스는 [(N-1)/2]
• 왼쪽 자식은 [(N*2)+1]
• 오른쪽 자식은 [(N*2)+2]

를 이용하여 구현했다.

 

Push는 가장 마지막 인덱스부터 시작해서 도장깨기 식으로 부모와 계속 스왑하는 형식!

void push(int value)
{
    heap.push_back(value);
    int curIndex = static_cast<int>(heap.size()) - 1;

    while (curIndex >= 0)
    {
        int parent = (curIndex - 1) / 2;

        // 도장깨기
        if (heap[parent] < heap[curIndex])
        {
            swap(heap[parent], heap[curIndex]);
            curIndex = parent;
        }
        else break;
    }
}

Pop은 0번째 인덱스를 반환하되, 재정렬을 한다.

재정렬은 가장 마지막에 있는 요소를 첫번째로 만든 다음 아래로 역도장깨기를 하면서 정렬한다.

int pop()
{
    int value = heap[0];
    heap[0] = heap.back();
    heap.pop_back();

    int curIndex = 0;
    int next = 1;

    // top부터 시작해서 내려오기
    // => 재정렬
    while (next <= static_cast<int>(heap.size()) - 1)
    {
        if (next < static_cast<int>(heap.size()) - 1)
        {
            // 왼쪽, 오른쪽 자식 비교
            if (heap[next] < heap[next + 1])
                ++next;
        }

        // 지금이 더 크다면 끝냄
        if (heap[next] < heap[curIndex]) break;
        else swap(heap[next], heap[curIndex]);

        curIndex = next;
        next = next * 2 + 1;
    }

    return value;
}

처음은 다음으로 갈 요소를 왼쪽, 오른쪽 중에 더 큰 요소로 결정한다.

 

현재 요소가 다음에 갈 요소보다 크다면 그 자리에서 끝내고, 아니라면 현재 요소는 더 내려간다.

 

이것을 반복하며 재정렬해주면 우선순위 큐의 pop을 구현할 수 있다.

 

 

오랜만에 최대 힙을 통해 우선순위 큐를 만드는 것을 공부해서 유익했다. stl을 쓰더라도 그 안에 구현 방식을 까먹지 않게 자꾸자꾸 복습해야겠다.