Heap(힙) & Priority Queue(우선순위 큐)

힙(Heap)

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를

기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

::A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다::

힙에는 두 가지 종류가 있으며 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙',

부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인

이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며,

이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

*출처 : 위키백과

최소 힙(Min Heap)의 구현

최소 힙을 구현할때는 배열이 가장 좋고, 배열로 힙을 구현하면 힙의 마지막 노드의 위치를 빠르게 알 수 있고,

완전 이진 트리이므로 따로 링크를 보관하지 않아도 되는 등의 장점을 지니고 있다.

완전 이진 트리를 배열로 나타낼 때, 깊이 n의 노드는 배열의 {2^n-1} & {2^(n+1)-2} 번 요소에 저장을 하게 된다.

깊이 0의 루트 노드는 배열의 0번째 요소로 들어간다.

*참고 : http://blog.eairship.kr/249

우선순위 큐(Priority Queue)

컴퓨터 과학에서 우선순위 큐는 큐나 스택과 비슷한 축약 자료형이고, 각 원소들이 우선순위를 갖고 있다.

우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.

만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다.

1) 스택 : 원소들은 후입 선출 순으로 처리된다.

2) 큐 : 원소들은 선입 선출 순으로 처리된다.

우선순위 큐가 힙이라는 것은 널리 알려진 오류다. 우선순위 큐는 "list"나 "map"과 같은 추상적인 개념이다.

마치 list는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다른 방법을 이용해 구현될 수 있다.

우선순위 큐는 최소한 다음의 연산이 지원되어야 한다.

1) insert_with_priority : 하나의 원소를 우선순위를 지정해 큐에 추가한다.

2) pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다.

*출처 : 위키백과

#include<iostream>
#include<queue>
 
using namespace std;
 
#define DEFAULT_SIZE 100001
 
template <typename T>
class Heap {
public:
    Heap();
    Heap(int);
    ~Heap();
    void insert(const T&);
    void swap(T* a, T* b);
    void print();
    T top();
    T pop();
private:
    T* heap;
    int capacity;
    int size;
};
 
template <typename T>
Heap<T>::Heap() {
    heap = new T[DEFAULT_SIZE];
    size = 0;
    capacity = DEFAULT_SIZE;
}
 
template <typename T>
Heap<T>::Heap(int Capacity) : capacity(Capacity)
{
    heap = new T[Heap::capacity];
    size = 0;
}
 
template <typename T>
Heap<T>::~Heap()
{
    delete[] heap;
}
 
template <typename T>
void Heap<T>::swap(T* a, T* b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}
 
template <typename T>
void Heap<T>::insert(const T& data)
{
    int usedPos = size;
    int parentPos = (usedPos - 1) / 2;
 
    if (size == capacity)
    {
        cout << "Full Heap\n";
        return;
    }
 
    heap[size] = data;
 
    while (usedPos >= 0 && heap[usedPos] < heap[parentPos]) {
        swap(&heap[usedPos], &heap[parentPos]);
        usedPos = parentPos;
        parentPos = (usedPos - 1) / 2;
    }
 
    size++;
}
 
template <typename T>
T Heap<T>::top() {
    if (size == 0) return 0;
    else return heap[0];
}
 
template <typename T>
T Heap<T>::pop()
{
    if (size == 0) return 0;
 
    int selectChild = 0;
    int parentPos = 0;
    int leftPos = 1;
    int rightPos = 2;
    T value = heap[0];
 
    size--;
    heap[0] = NULL;
    swap(&heap[0], &heap[size]);
    while (1) {
        if (leftPos >= size) break;
        else if (rightPos >= size) selectChild = leftPos;
        else selectChild = heap[leftPos] > heap[rightPos] ? rightPos : leftPos;
 
        if (heap[selectChild] < heap[parentPos])
        {
            swap(&heap[parentPos], &heap[selectChild]);
            parentPos = selectChild;
        }
        else break;
 
        leftPos = 2 * parentPos + 1;
        rightPos = leftPos + 1;
    }
 
    return value;
}
 
 
template <typename T>
void Heap<T>::print()
{
    for (int i = 0; i < size; i++) {
        cout << heap[i] << " ";
    }
    cout << "\n";
}
 
int main() {
 
    int maxSize = 6;
    int input;
    Heap<int> heap(maxSize);
 
    for (int i = 0; i < maxSize; i++)
    {
        cin >> input;
        heap.insert(input);
    }
    heap.print();
 
    cout << heap.pop() << endl;
 
    heap.print();
 
    cout << heap.pop() << endl;
 
    heap.print();
 
    return 0;
}