11279번 최대 힙

최대 힙 구현 문제이다.

구현 과정, 논리(로직)를 익숙해지도록 구현해봐야겠다.

https://www.acmicpc.net/problem/11279

<C++로 구현한 최대 힙>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
vector<int> heap;
 
// 정수를 담는 최대 힙 heap에 새 원소 newValue를 삽입한다.
void push_heap(int newValue)
{
    // 힙 맨 끝에 newValue를 삽입한다.
    heap.push_back(newValue);
 
    // 현재 newValue의 위치
    int index = heap.size() - 1;
 
    // 루트에 도달하거나, newValue 이상의 원소를 가진 조상을 만날 때 까지 진행
    while (index > 0 && heap[(index - 1) / 2] < heap[index])
    {
        swap(heap[index], heap[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}
 
// 맨 위의 루트 노드에서 하나씩 내려가면서 비교하면서 힙 모양 만들기
int pop_heap()
{
    // heap 비어있으면, 0을 return
    if (heap.empty()) return 0;
 
    // 반환 할, 제일 큰 원소
    int ret = heap[0];
 
    // heap의 맨 끝에서 값을 가져와서 루트에 덮어 씌운다.
    heap[0] = heap.back();
 
    // 맨 끝 heap 삭제
    heap.pop_back();
 
    int here = 0;
 
    while (true)
    {
        int left = 2 * here + 1; // 왼쪽 자식
        int right = 2 * here + 2; // 오른쪽 자식
 
        // 리프에 도달한 경우
        if (left >= heap.size()) break;
        
        // heap[here]가 내려갈 위치를 찾는다.
 
        int next = here;
 
        if (heap[next] < heap[left])
        {
            next = left;
        }
 
        if (right < heap.size() && heap[next] < heap[right])
        {
            next = right;
        }
 
        // 위에서 next가 갱신되지 않았다면
        if (next == here) break;
 
        swap(heap[here], heap[next]);
 
        here = next;
    }
 
    return ret;
}
 
int main(void)
{
    int N = 0;
    
    scanf("%d", &N);
 
    while (N--)
    {
        int x = 0;
 
        scanf("%d", &x);
 
        if (x == 0) printf("%d\n", pop_heap());
        else if (x >= 1) push_heap(x);
    }
 
    return 0;
}

<C로 구현한 최대 힙>

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
int *heap;
int N = 0;
int last_index = -1;
 
// 정수를 담는 최대 힙 heap에 새 원소 newValue를 삽입한다.
void push_heap(int newValue)
{
    // 힙 맨 끝에 newValue를 삽입한다.
    heap[++last_index] = newValue;
 
    // 현재 newValue의 위치
    int index = last_index;
 
    while (index > 0 && heap[(index - 1) / 2] < heap[index])
    {
        int temp = 0;
 
        temp = heap[(index - 1) / 2];
        heap[(index - 1) / 2] = heap[index];
        heap[index] = temp;
 
        index = (index - 1) / 2;
    }
}
 
// 맨 위의 루트 노드에서 하나씩 내려가면서 비교하면서 힙 모양 만들기
int pop_heap()
{
    // heap 비어있으면, 0을 return
    if (heap[0] == -1) return 0;
 
    // 반환 할, 제일 큰 원소
    int ret = heap[0];
 
    // heap의 맨 끝에서 값을 가져와서 루트에 덮어 씌운다.
    heap[0] = heap[last_index];
 
    // 맨 끝 heap 삭제
    heap[last_index] = -1;
 
    --last_index;
 
    int here = 0;
 
    while (1)
    {
        int left = 2 * here + 1; // 왼쪽 자식
        int right = 2 * here + 2; // 오른쪽 자식
 
        // 리프에 도달한 경우
        if (left >= last_index + 1) break;
 
        // heap[here]가 내려갈 위치를 찾는다.
 
        int next = here;
 
        if (heap[next] < heap[left])
        {
            next = left;
        }
 
        if (right < last_index + 1 && heap[next] < heap[right])
        {
            next = right;
        }
 
        // 위에서 next가 갱신되지 않았다면
        if (next == here) break;
 
        int temp = heap[here];
        heap[here] = heap[next];
        heap[next] = temp;
 
        here = next;
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d", &N);
 
    heap = (int*)malloc(sizeof(int)*N);
 
    memset(heap, -1, sizeof(heap));
    
    while (N--)
    {
        int x = 0;
 
        scanf("%d", &x);
 
        if (x == 0) printf("%d\n", pop_heap());
        else if (x >= 1)
        {    
            push_heap(x);
        }
    }
 
    return 0;
}