[알고리즘] 힙 트리를 이용한 우선순위 큐

우선순위 큐는 큐처럼 선입선출이 아닌 값이 큰 순서대로 pop한다.

우선순위 큐는 힙 트리를 이용해 구현할 수 있고 힙 트리는

데이터가 꽉 차 있는 형태이기 때문에 데이터를 배열로 표현할 수 있다.

 

	void push(const T& value)
	{
		heap.push_back(value);
		int now = static_cast<int>(heap.size()) - 1;

		while (now > 0)
		{
			int parent = (now - 1) / 2;
			if (heap[parent] < heap[now])
			{
				::swap(heap[parent], heap[now]);
				now = parent;
			}
			else
				break;
		}
	}

 

힙 트리를 배열로 표현할 때 i 번째 노드의 부모는 (i-1)/2 이므로 이를 이용해 현재 노드와 부모 노드의 도장 깨기를 시전.

현재 노드가 루트 노드 되기 전까지 도장 깨기를 계속 시전한다.

 

void pop()
	{
		heap[0] = heap.back();
		heap.pop_back();

		int now = 0;
		
		while (true)
		{
			int change = now;

			int left = change * 2 + 1;
			int right = change * 2 + 2;
			//왼쪽 노드가 트리 범위 밖일 때 끝!
			if (left >= heap.size())
				break;

			if (heap[change] < heap[left])
				change = left;
			//현재노드와 왼쪽노드 중 더 큰값을 오른쪽 노드와 다시 비교
            		//right < heap.size()는 왼쪽 노드만 있는 경우때문에 체크
			if (right < heap.size() && heap[change] < heap[right])
				change = right;
			//양쪽 노드가 부모노드보다 작을 경우 끝!
			if (now == change)
				break;

			::swap(heap[now], heap[change]);
			now = change;
		}
	}

 

pop할 때는 가장 큰 값이 빠지므로 루트 노드가 빠지게 되고 맨 마지막 노드가 루트 노드 자리로 간다.

그리고 역 도장깨기를 시전하는데 양쪽 노드가 부모노드보다 작거나 왼쪽 노드가 트리 범위 밖일 때 루프가 끝난다.

그러니까 현재노드와 좌측, 우측 노드를 비교해 더 큰 값과 교체한다.