[자료구조] 힙(Heap)

우선 순위 큐(Priority Queue)

우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다.

또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다.

template <class T>
class MaxPQ{
public:
	virtual ~MaxPQ(){ }		// 가상 파괴자
    virtual bool IsEmpty() const = 0;	// 우선순위 큐가 공백이면 true 반환
    virtual const T& Top() const = 0;	// 최대 원소에 대한 참조를 반환
    virtual void Push(const T&) = 0;	//우선순위 큐에 원소를 삽입
    virtual void Pop() = 0;		// 최대 우선순위를 가진 원소 삭제
};

시간 복잡도

 

<무순서 선형 연결리스트로 구현>

• IsEmpty(): O(1)
• Push(): O(1)
• Top(): Θ(n)
• Pop(): Θ(n)

 

<최대 힙>

• IsEmpty(): O(1)
• Top(): O(1)
• Push(): O(log n)
• Pop(): O(log n)

힙(Heap)의 소개

최대(최소) 트리: 각 노드의 키 값이 그 자식의 키 값보다 작기(크지) 않은 트리

최대 힙(Max heap): 최대 트리이면서 완전 이진 트리

최소 힙(Min heap): 최소 트리이면서 완전 이진 트리

 

최대 힙에서의 삽입

위 그림은 최대 힙에 23을 새로 삽입하는 예시이다.

template <class T>
void MaxHeap<T>::Push(const T& e)
{ // 최대 힙에 e를 삽입
	if (heapSize == capacity) { // 기존 공간이 꽉 찬 경우 크기를 2배로
    	changeSize1D(heap, capacity, 2*capacity);
        capacity *= 2;
    }
    int currentNode = ++heapSize; // 기존 마지막 원소의 다음 위치에서 시작
    while (currentNode != 1 && heap [currentNode / 2 < e)
    { // 최대 힙의 조건이 만족할 때까지 root로 올라감
    	heap[currentNode] = heap[currentNode/2]; // 부모 노드를 현재 위치로 이동
        currentNode /= 2; // 부모 노드 위치로 이동
    }
    heap[currentNode] = e;
}

시간 복잡도는 O(log n)이다.

 

최대 힙에서의 삭제

위 그림은 최대 힙에서 루트를 삭제하는 예시이다.

template <class T>
void MaxHeap<T>::Pop() {
	if (IsEmpty()) throw "Heap is empty. Cannot delete.";
    heap[1].~T();
    T lastE = heap[heapSize--]; 
    int currentNode = 1;
    int child = 2;
    while (child <= heapSize) {
    	if (child < heapSize && heap[child] < heap[child+1]) child++;
        if (lastE >= heap[child]) break;
        heap[currentNode] = heap[child];
        currentNode = child;
        child *= 2;
    }
    heap[currentNode] = last;
}

최대 힙에서 원소를 삭제할 떄는 힙의 루트에서 삭제한다.