[SCCC 스터디] 힙 정렬 직접 구현

3일차에서 최소 힙을 짰었는데 너무 드럽게 짜서 다시 간단하게 짜봤다.

또한 최소 힙을 짜면서 최대 힙도 다시 짜봤다.

1. 최대 힙

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int heap[200000];
int Size = 1;
 
void push(int data)
{
    heap[++Size] = data;
    int idx = Size;
    while (idx > 1)
    {
        if (heap[idx] > heap[idx / 2])
        {
            swap(heap[idx], heap[idx / 2]);
        }
        idx /= 2;
    }
}
 
int pop()
{
    if (Size == 1)return 0;
    int top = heap[1];
    heap[1] = heap[Size];
    heap[Size--] = 0;
    int idx = 1;
    while (1)
    {
        if (heap[idx] < heap[idx * 2] || heap[idx] < heap[idx * 2 + 1])
        {
            if (heap[idx * 2] > heap[idx * 2 + 1])
            {
                swap(heap[idx * 2], heap[idx]);
                idx = idx * 2;
            }
            else
            {
                swap(heap[idx * 2 + 1], heap[idx]);
                idx = idx * 2 + 1;
            }
        }
        else
        {
            break;
        }
    }
    return top;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int input;
    while (n--)
    {
        cin >> input;
        if (!input)
        {
            cout << pop() << '\n';
        }
        else
        {
            push(input);
        }
    }
    return 0;
}

2.  최소 힙

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
int heap[200000];
int Size = 0;
 
void push(int data)
{
    heap[++Size] = data;
    int idx = Size;
    while (idx > 1)
    {
        if (heap[idx] < heap[idx / 2])
        {
            swap(heap[idx], heap[idx / 2]);
            idx /= 2;
        }
        else break;
    }
}
 
int pop()
{
    if (!Size)return 0;
    int top = heap[1];
    heap[1] = heap[Size];
    heap[Size--] = -1;
    int idx = 1;
 
    while (1)
    {
        bool left = heap[idx * 2] > 0;
        bool right = heap[idx * 2 + 1] > 0;
 
        if ((left && heap[idx * 2] < heap[idx]) || (right && heap[idx * 2 + 1] < heap[idx]))
        {
            if (right && left)
            {
                if (heap[idx * 2] > heap[idx * 2 + 1])
                {
                    swap(heap[idx], heap[idx * 2 + 1]);
                    idx = idx * 2 + 1;
                }
                else
                {
                    swap(heap[idx], heap[idx * 2]);
                    idx = idx * 2;
                }
            }
            else if (right)
            {
                swap(heap[idx], heap[idx * 2 + 1]);
                idx = idx * 2 + 1;
            }
            else if (left)
            {
                swap(heap[idx], heap[idx * 2]);
                idx = idx * 2;
            }
        }
        else break;
    }
    return top;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int input;
        cin >> input;
        if (input) push(input);
        else cout << pop() << '\n';
    }
}