Heap

Heap

heap 자료구조 구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void swap(int *n1, int *n2)
{
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

class Heap
{
    private:
    vector<int> heap;
    
    /*
    계산상의 편의를 위해 0번 인덱스를 사용하지 않음
    */
    public:
    Heap()
    {
        heap.push_back(0);
    }
    
    /*
    0번 인덱스를 사용하지 않기 위해 push한 데이터를 고려하여 size - 1 반환
    */
    int size()
    {
        return heap.size() - 1;
    }
    
    int top()
    {
        return heap[1];
    }
    
    void push(int value)
    {
        int child = heap.size();
        int parent = child / 2;
        
        heap.push_back(value);
        while (child > 1 && heap[parent] < heap[child])
        {
            swap(&heap[child], &heap[parent]);
            child = parent;
            parent = child / 2;
        }
    }
    
    void pop()
    {
        int child = 2;
        int parent = 1;
        
        heap[1] = heap.back();
        heap.pop_back();
        if (child + 1 <= heap.size())
        {
            child = (heap[child] > heap[child + 1]) ? child : child + 1;
        }
        while (child <= heap.size() && heap[parent] < heap[child])
        {
            swap(&heap[parent], &heap[child]);
            parent = child;
            child = child * 2;
            if (child + 1 <= heap.size())
            {
                child = (heap[child] > heap[child + 1]) ? child : child + 1;
            }
        }
    }
};