[트리] Tree 5: 우선순위 큐와 이진 힙

1. 우선순위 큐와 이진 힙

 

 

트리와 밀접하게 연관된 다른 자료 구조로 우선순위 큐가 있다.

 

이것은 순서대로 기다리고 있는 자료들을 저장하는 자료구조이다.

 

일반 큐와는 다른 점은 

 

가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다는 것이다.

 

만약 이것을 균형잡힌 트리를 사용하여 우선순위 큐를 구현하게되면

 

삽입 삭제 전부 lgn 시간에 수행할 수 있다.

 

또 이것은 힙(heap)으로도 구현할 수 있으며 이는 훨씬 단순한 구조이다.

 

힙은 가장 큰 원소, 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리로,(최대힙 max heap 최소힙 min heap)

 

삽입연산과 가장 큰 원소를 삭제하는 연산 모두 O(lgn)시간에 수행가능하다.

 

우선순위와 자료의 쌍을 담는 이진 힙을 만들고, 우선순위 비교를 통해 연산을 수행한다면, 우선순위 큐를 구현할 수 있다.

 

 

힙은 표준라이브러리에 대부분 포함되어있다.

 

 

2. 힙의 정의와 구현

 

힙은 특정한 규칙을 만족하도록 구성된 이진 트리이다.

 

그 규칙은 최대 원소를 빠르게 찾도록 되어있다.

 

가장 중요한 규칙은 힙의 대소 규칙이다.

 

부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이어야 한다.

 

부모 자식간에만 성립. 왼쪽 오른쪽 상관 없다.

 

이 규칙에 의해 가장 큰 원소는 항상 트리의 루트에 들어간다.

 

힙은 트리의 높이를 항상 일정하게 유지하기위해 다음과 같은 규칙도 있다.

 

마지막 레벨을 제외한 모든 레벨에 노드가 꽉차있어야한다.

 

마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워야한다.

 

레벨: 같은 높이에 있는 원소들의 집합

 

이러한 규칙 덕분에 개수만 알면 트리의 모양을 알 수 있고 모양규칙이라고도 한다.

 

 

배열을 이용한 힙의 구현

트리에 포함된 노드의 개수를 알면 트리 전체의 구조를 알 수 있기 때문에

구현하기 간단하다.

 

위 그림 처럼 '배열'로 전체 트리를 표현할 수 있기 때문이다.

 

.A[i] 에 대응되는 노드의 왼쪽 자손은 A[2*i + 1]에 대응된다.

..A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i + 2]에 대응된다.

...A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응된다. (나누셈 결과는 반올림된다)

 

이처럼 힙의 노드들은 일차원 배열에 일대일 대응된다,

 

배열을 사용함으로 써 이진 검색 트리를 구현하는 것 보다 간결해 우선순위 큐를 구현하는데

자주 쓰인다.

 

새 원소 삽입

 

힙의 모든 조건을 유지하면서 새 원소를 삽입해야한다.

 

루트에서 시작해 새 원소의 위치를 찾는다고 해보자.

 

우선 루트가 가진 원소와 새 원소를 비교해본다.

더 큰 원소가 올경우 대체되고, 아닐 경우 서브 트리중 한곳으로들어가야한다.

 

서브트리중 어느것을 선택하는지는 모양 규칙을 먼저 만족시키면 알 수 있다.

 

모양 규칙에 의해 새 노드는 항상 배열의 맨 끝에 추가되어야 하기 때문이다,

 

마지막에 추가되고 부모와 비교를통해 위로 올라간다.

 

이런 동작은 트리의 높이에 지배되므로 O(lgn) 만에 수행된다.

 

 

 

 

최대 원소 꺼내기

 

 

배열을 이용해 최대원소를 접근하는 법은 그냥 첫 원소를 보면된다.

 

하지만 이 원소를 꺼내어 없앨때는 힙의 모양을 유지하기위해 별도의 합치기 연산이 필요하다.

 

원소를 하나 꺼냄으로써 힙의 전체 사이즈는 1이 줄어든다는 점을 이용해서 합치기 연산을 구현할 수 있다.

 

원소를 꺼낸뒤 루트에 집어 넣는다, 그런다음 아래 두개의 노드의 크기 비교를 통해 더 큰 쪽과 루트의 자리를 바꾼다.

 

이 후 쭉 내려가면서 맞바꾸다 보면 노드 두개가 자기보다 작은것이면 힙이 완성된다.

 

이 연산또한 높이에 지배되기 때문에 O(lgn)의 수행시간이 걸린다.

 

다음은 원소 삽입과 삭제를 구현한 코드이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
 
void push_heap(vector<int>& heap, int newValue) {
    heap.push_back(newValue);
    int idx = heap.size() - 1;
    
    while(idx > 0 && heap[(idx - 1)/2] < heap[idx]) {
        swap(heap[idx], heap[(idx-1)/2]);
        idx = (idx - 1)/2;
    }
}
 
int pop_heap(vector<int>& heap) {
    int ret = heap[0];
    int idx = 0;
    int size = heap.size() - 1;
    heap[0] = heap.back();
    heap.pop_back();
    
    while(1) {
 
        if(idx*2 + 1 >= size) break;
        int next = idx;
 
        if(heap[idx] < heap[idx*2+ 1])
            next = idx * 2 + 1;
        if(idx * 2 + 2 < size && heap[next] < heap[idx*2 + 2])
            next = idx * 2 + 2;
 
        if(next == idx) break;
        swap(heap[idx], heap[next]);
        idx = next;
    }
    return ret;
}
 
int main()
{
    vector<int> a;
    int size= 0;
    cin>>size;
    for(int i = 0; i < size ; i++)
    {
        int k = 0;
        cin>>k;
        push_heap(a, k);
    }
    for(int i = 0 ; i < size; i++)
     cout<<a[i]<<" ";
    
    cout<<"\n";
    for(int i = 0; i < size; i++)
        cout<<pop_heap(a)<<" ";
    
    cout<<"\n";
}

 

다른 연산들

힙을 만드는 연산:

    힙을 O(N)만에 만드는 연산. 원소가 담긴 배열로 힙을 만든다. 어차피 원소를 다 빼는 시간은 똑같으므로 의미는 없다.

 

힙 정렬:

    원소들을 꺼낼 때 항상 정렬된 순서대로 반환된다는 점을 이용한 것, 

    따라서 주어진 배열을 힙으로 만든 뒤 모든 원소들을 꺼내서 반환 순서대로 배열하면 정렬결과가 됨.

    원소를 삭제할때 마지막 인덱스가 비는점을 이용하여 최대 원소를 삭제하는 곳에 두면 자동적으로 정렬됨.

    최악의 경우도 nlgn, 추가 메모리가 필요없다는 점에서 병합정렬과 다르다.

 

힙 원소 값 변경:

    우선순위 큐를 구현할 때 유용하게 사용된다.

    우선순위가 높아졌을때 사용, 새 원소 삽입과 비슷하게 구현된다.

    이를 구현하려면 힙의 원소의 위치를 기억하고 있는 별도의 변수가 필요하다.

 

 

#include <iostream>
#include <vector>
#include <utility>
#include <map>

namespace nlib
{
	template <class T1, class T2>
	class maxHeap
	{
	private:
		std::vector<std::pair<T1, T2> > heap;
		std::map<T2, int> keyPos;
	public:
		maxHeap()
		{
			heap = std::vector<std::pair<T1, T2> >();
			keyPos = std::map<T2, int>();
		}
		void swapPos(int a, int b);
		void push(std::pair<T1, T2> item);
		void pop();
		std::pair<T1, T2> top();
		bool update(std::pair<T1, T2> item);
		int size();
		void erase(T2 key);
		int find(T2 key);
		bool empty();
		int adjustDown(int idx);
		int adjustUp(int idx);
	};
}
namespace nlib
{
	template <class T1, class T2>
	void maxHeap<T1, T2>::swapPos(int a, int b)
	{
		int aPos = keyPos[heap[a].second];
		int bPos = keyPos[heap[b].second];
		keyPos[heap[a].second] = bPos;
		keyPos[heap[b].second] = aPos;
		std::pair<T1, T2> tmp = heap[a];
		heap[a] = heap[b];
		heap[b] = tmp;
	}
	template <class T1, class T2>
	int maxHeap<T1, T2>::adjustDown(int parent)
	{
		int size = this->size();
		while (true) {
			if (parent * 2 + 1 >= size) break;
			int next = parent;

			if (heap[parent].first < heap[parent * 2 + 1].first)
				next = parent * 2 + 1;
			if (parent * 2 + 2 < size && heap[next].first < heap[parent * 2 + 2].first)
				next = parent * 2 + 2;
			if (next == parent) break;
			swapPos(parent, next);
			parent = next;
		}
		return parent;
	}
	template <class T1, class T2>
	int maxHeap<T1, T2>::adjustUp(int child)
	{
		while (heap[(child - 1) / 2].first < heap[child].first)
		{
			swapPos((child - 1) / 2, child);
			child = (child - 1) / 2;
		}
		return child;
	}
	template <class T1, class T2>
	void maxHeap<T1, T2>::push(std::pair<T1, T2> item)
	{
		if (keyPos.count(item.second) == 0)
		{
			heap.push_back(item);
			keyPos[item.second] = size() - 1;
			if (size() != 1)
				adjustUp(size() - 1);
		}
	}

	template <class T1, class T2>
	void maxHeap<T1, T2>::pop()
	{
		if (size() == 0)
		{
			std::cout << "empty\n";
			return;
		}
		swapPos(0, size() - 1);
		
		keyPos.erase(heap.back().second);
		heap.pop_back();
		if (size() == 0)
			keyPos.clear();
	}
	template <class T1, class T2>
	void maxHeap<T1, T2>::erase(T2 key)
	{
		int pos = find(key);
		swapPos(pos, size() - 1);
		heap.pop_back();
		adjustUp(adjustDown(pos));
	}
	template <class T1, class T2>
	std::pair<T1, T2> maxHeap<T1, T2>::top()
	{
		if (size() == 0)
		{
			std::cout << "empty\n";
		}
		return heap[0];
	}
	template <class T1, class T2>
	bool maxHeap<T1, T2>::update(std::pair<T1, T2> item)
	{
		int pos = find(item.second);
		if (pos == -1) return false;
		heap[pos] = item;
		adjustUp(adjustDown(pos));
		return true;
	}
	template <class T1, class T2>
	int maxHeap<T1, T2>::size()
	{
		return (int)heap.size();
	}
	template <class T1, class T2>
	int maxHeap<T1, T2>::find(T2 key)
	{
		if (keyPos.count(key) == 0|| size()==0)
			return -1;
		return keyPos[key];
	}
	template <class T1, class T2>
	bool maxHeap<T1, T2>::empty()
	{
		return size() == 0;
	}

}

 

- 알고리즘 문제해결전략 723p