힙 heap

2022. 6. 2. 17:45

힙

완전이진트리의 일종으로 우선순위 큐를 우하여 만들어진 자료구조

최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 구조

완전이진트리 - 노드를 삽입할때 왼쪽부터 차례대로 삽입하는 트리

최대 힙	최소 힙

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전이진트리	부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전이진트리

완전이진트리는 배열로 구현한다.

필자는 배열이 재할당을 알아서 해주기위해 vector를 사용

또한 이 코드는 최대 힙으로 구현

#include <iostream>
#include <vector>

using namespace std;

class Heap
{
    int size = 0;
    vector<int> heap; 
public:
    void push(int value) 
    {
        heap.push_back(value);
        sort(size);
        size++;
    }

    void sort(int _size)
    {
        int c = _size;
        int p = (c - 1) / 2;

        while (c > 0 && heap[c] > heap[p])
        {
            swap(c, p);
            c = p;
            p = (c - 1) / 2;
        }
    }

    void swap(int a, int b) {
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
    }

    int pop()
    {
        if (size == 0)
        {
            cout << "비어있습니다." << endl;
            return 0;
        }

        int poll = heap[0];
        heap[0] = heap[--size];
        popsort();

        return poll;
    }

    void popsort()
    {
        int p = 0;
        int c = 1;

        while(c <= size) {
            if(c < size && heap[c] < heap[c + 1])
                c++;
            if(heap[c] <= heap[p]) break;

            swap(c, p);
            p = c;
            c = c * 2 + 1;
        }
    }


    void print()
    {
        for(int i=0; i<heap.size(); i++)
            cout << heap[i] << " ";
        cout << endl;
    }

};

int main()
{
    Heap h;

    h.push(1);
    h.push(10);
    h.push(2);
    h.push(6);
    h.push(3);
    h.push(7);
    h.push(5);
    h.push(6);
    h.push(8);

    h.print();
    cout << "pop: " << h.pop() << endl;
    h.print();
}

특정 노드의 배열 인덱스가 current라고 한다면