Priority Queues - 편집 역사

Pinkgo: /* Faster Way to Build a Heap */

2025-09-25T00:16:39Z

Faster Way to Build a Heap

← 이전 판		2025년 9월 25일 (목) 00:16 판
114번째 줄:		114번째 줄:
	</syntaxhighlight>		</syntaxhighlight>
	이는 배열 s[]를 통째로 복사 후, 내부 노드(leaf 아님)부터 거꾸로 bubble_down 실행하는 방식이다. 해당 알고리즘의 시간 복잡도는 아래와 같이 계산할 수 있다:		이는 배열 s[]를 통째로 복사 후, 내부 노드(leaf 아님)부터 거꾸로 bubble_down 실행하는 방식이다. 해당 알고리즘의 시간 복잡도는 아래와 같이 계산할 수 있다:
	* 높이가 h인 노드는 최대 <math>\frac{n}{2^{h+1}}</math>개 존재		* 높이가 h인 노드는 최대 <math>\lceil\frac{n}{2^{h+1}}\rceil</math>개 존재
	* 높이가 h인 각 노드의 bubble_down 비용은 <math>O(h) = O(log(n))</math>		* 높이가 h인 각 노드의 bubble_down 비용은 <math>O(h) = O(log(n))</math>
	<math>\therefore\,\, O(\sum^{log(n)}_{h=0}\frac{n}{2^{h+1}}\cdot h) = O(n \sum^{log(n)}_{h=0}\frac{h}{2^{h}})</math>		<math>\therefore\,\, O(\sum^{log(n)}_{h=0}\frac{n}{2^{h+1}}\cdot h) = O(n \sum^{log(n)}_{h=0}\frac{h}{2^{h}})</math>

Pinkgo: /* Heap */

2025-09-20T10:45:17Z

Heap

← 이전 판		2025년 9월 20일 (토) 10:45 판
21번째 줄:		21번째 줄:

	==Heap==		==Heap==
			[[파일:Figure 1. Binary Heaps.png\|가운데\|섬네일\|500x500픽셀\|Figure 1. Binary Heaps]]
	힙(Heap)은 완전 이진트리(complete binary tree) 기반의 자료구조이다. 즉, 모든 레벨이 다 채워져 있고, 마지막 레벨만 예외적으로 왼쪽부터 채워지는 트리를 기반으로 한다. 힙 자료 구조는 아래와 같은 조건을 만족해야 한다.		힙(Heap)은 완전 이진트리(complete binary tree) 기반의 자료구조이다. 즉, 모든 레벨이 다 채워져 있고, 마지막 레벨만 예외적으로 왼쪽부터 채워지는 트리를 기반으로 한다. 힙 자료 구조는 아래와 같은 조건을 만족해야 한다.
	# 리프(leaf)노드는 마지막 두 층에서만 리프가 분포할 수 있다.		# 리프(leaf)노드는 마지막 두 층에서만 리프가 분포할 수 있다.
32번째 줄:		33번째 줄:
	# 오른쪽 자식: 2k+1		# 오른쪽 자식: 2k+1
	# 부모: ⌊k/2⌋		# 부모: ⌊k/2⌋
	# heap의 루트 노드의 인덱스는 "1"		#heap의 루트 노드의 인덱스는 "1"
	이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.		이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.

Pinkgo: /* Applications of Priority Queues */

2025-09-20T10:32:03Z

Applications of Priority Queues

← 이전 판		2025년 9월 20일 (토) 10:32 판
126번째 줄:		126번째 줄:
	사실은 일반적인 stack(LIFO)이나 queue(FIFO)도 사실은 특수한 형태의 우선순위 큐이다. stack은 가장 최근에 들어온 원소가 우선순위가 높고, queue는 가장 먼저 들어온 원소가 우선순위가 높은 것이다.		사실은 일반적인 stack(LIFO)이나 queue(FIFO)도 사실은 특수한 형태의 우선순위 큐이다. stack은 가장 최근에 들어온 원소가 우선순위가 높고, queue는 가장 먼저 들어온 원소가 우선순위가 높은 것이다.

	우선순위 큐는 시뮬레이션(simulation) 에서 매우 자주 활용된다. 시뮬레이션은 시간의 흐름에 따라 사건(event)이 발생하는데, 각 사건의 발생 시간이 다르다. 이때 우선순위 큐를 이용하면 “가장 빨리 일어날 사건(최소 시간)”을 효율적으로 뽑아낼 수 있다. 예를 들면 공항에서 다음 비행기 착륙, 주차장에서 다음 차량 입출차 등이 있다.		우선순위 큐는 시뮬레이션(simulation) 에서 매우 자주 활용된다. 시뮬레이션은 시간의 흐름에 따라 사건(event)이 발생하는데, 각 사건의 발생 시간이 다르다. 이때 우선순위 큐를 이용하면 “가장 빨리 일어날 사건(최소 시간)”을 효율적으로 뽑아낼 수 있다. 예를 들면 공항에서 다음 비행기 착륙, 주차장에서 다음 차량 입출차 등이 있다.

			또한 heap은 그 특성 덕에 정렬 알고리즘에 응용되어 heap sort 알고리즘을 만드는데 쓰인다. 자세한 내용은 [[Sorting Problem#Heap Sort\|heap sort]] 문서를 참조해 주십시오.

	==각주==		==각주==

Pinkgo: /* Implementing Heap */

2025-09-20T10:29:41Z

Implementing Heap

@@ 97번째 줄: / 97번째 줄: @@
+}
 </syntaxhighlight>
 ==Applications of Priority Queues==

Pinkgo: /* Implementing Heap */

2025-09-20T09:57:40Z

Implementing Heap

← 이전 판		2025년 9월 20일 (토) 09:57 판
82번째 줄:		82번째 줄:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	void bubble_down(priority_queue *q, int p) {		void bubble_down(priority_queue *q, int p) {
	int c = pq_young_child(p);		int c = pq_young_child(p); //자식 노드의 인덱스(c = 2p)
	int min_index = p;		int min_index = p; //min_index는 p, 2p, 2p+1 중에서 가장 작은 원소의 인덱스 추적
	for (int i = 0; i <= 1; i++) { // ~~두 자식과 비교~~		for (int i = 0; i <= 1; i++) { // 왼쪽(i=0), 오른쪽(i=1) 자식 검사
	if ((c + i) <= q->n) {		if ((c + i) <= q->n) { // 자식 인덱스가 힙 크기 범위 안이면
	if (q->q[min_index] > q->q[c + i]) {		if (q->q[min_index] > q->q[c + i]) {
	min_index = c + i;		min_index = c + i; // 더 작은 자식을 찾으면 갱신
	}		}
	}		}
	}		}
	if (min_index != p) {		if (min_index != p) {
	pq_swap(q, p, min_index);		pq_swap(q, p, min_index); // p와 q를 swap
	bubble_down(q, min_index);		bubble_down(q, min_index); // 재귀적으로 수행
	}		}
	}		}
	~~</syntaxhighlight>~~
	~~<syntaxhighlight lang="c">~~

	~~</syntaxhighlight>~~
	~~<syntaxhighlight lang="c">~~

	~~</syntaxhighlight>~~
	~~<syntaxhighlight lang="c">~~

	</syntaxhighlight>		</syntaxhighlight>

Pinkgo: /* Array-Based Heaps */

2025-09-20T09:50:23Z

Array-Based Heaps

← 이전 판		2025년 9월 20일 (토) 09:50 판
32번째 줄:		32번째 줄:
	# 오른쪽 자식: 2k+1		# 오른쪽 자식: 2k+1
	# 부모: ⌊k/2⌋		# 부모: ⌊k/2⌋
			# heap의 루트 노드의 인덱스는 "1"
	이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.		이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.

Pinkgo: /* Implementing Heap */

2025-09-20T09:46:58Z

Implementing Heap

← 이전 판		2025년 9월 20일 (토) 09:46 판
36번째 줄:		36번째 줄:

	==Implementing Heap==		==Implementing Heap==
			해당 문단에서는 힙의 삽입과 삭제를 하는 코드와, 이를 구현하기 위한 다른 코드들에 대해서 살펴본다. 이때 해당 문단은 min heap의 구현을 기준으로 살펴본다.

			===Constructing Heaps===
			Heap은 한번에 모든 원소들을 삽입하는 것이 아니라, 한번에 하나씩 트리에 원소들을 삽입하며 점진적(heapify by insertion)으로 생성한다. 이를 위해서 배열의 가장 왼쪽 빈 칸에 새 원소를 삽입하고, 부모보다 작으면 이를 swap(bubble-up)하는 방식이다. 이때 perfect balanced tree는 힙의 높이 h가 n개의 노드가 있을 때, h = ⌊log n⌋여야 한다. 이에 따라 시간 복잡도는 각각의 원소 삽입에 대한 시간 복잡도는 O(log(n))이며, 전체 n개의 노드에 대한 시간 복잡도는 O(n log(n))이다. 이를 구현하기 위한 코드는 아래와 같다:
			<syntaxhighlight lang="c">
			void pq_insert(priority_queue *q, item_type x) {
			if (q->n >= PQ_SIZE) { //PQ_SIZE는 배열이 저장할 수 있는 노드의 최대 크기
			printf("Warning: priority queue overflow!\n");
			} else {
			q->n = q->n + 1; //원소를 마지막 위치에 배치
			q->q[q->n] = x;
			bubble_up(q, q->n); //적절한 위치에 도달할 때 까지 swap
			}
			}
			</syntaxhighlight>
			해당 코드는 큐가 가득 차면 overflow를 경고한다. 그렇지 않으면 원소를 마지막 위치에 넣고, bubble_up으로 힙 조건을 유지한다. bubble_up 코드는 아래와 같이 구현된다.
			<syntaxhighlight lang="c">
			void bubble_up(priority_queue *q, int p) {
			if (pq_parent(p) == -1) return; // 루트 도달, 더 이상 부모 없음
			if (q->q[pq_parent(p)] > q->q[p]) { //부모가 자식보다 값이 크면 스왑
			pq_swap(q, p, pq_parent(p));
			bubble_up(q, pq_parent(p)); //재귀적으로 배치
			}
			}
			</syntaxhighlight>
			해당 bubble up 코드는 배열로 구현된 heap의 마지막에 삽입된 원소를 부모와 비교하며, 해당 원소를 재귀적으로 위로 올리는 방식이다.

			===Extracting the Minimum Element===
			Min heap의 구현에서 필수적인 코드 중 하나는 루트의 값(최솟값)을 꺼내고, 마지막 원소를 루트로 가져온 뒤 bubble_down으로 재정렬하는 것이다. 이는 아래와 같이 구현된다:
			<syntaxhighlight lang="c">
			item_type extract_min(priority_queue *q) {
			int min = -1;
			if (q->n <= 0) {
			printf("Warning: empty priority queue.\n");
			} else {
			min = q->q[1]; // 루트 값
			q->q[1] = q->q[q->n]; // 마지막 원소를 루트에 배치한다.
			q->n = q->n - 1;
			bubble_down(q, 1); // 이를 밑으로 bubble_down하면서 heap 조건을 복구한다.
			}
			return min;
			}
			</syntaxhighlight>
			아래는 이를 구현할 때 사용하는 bubble_down 함수를 구현하는 코드이다:
			<syntaxhighlight lang="c">
			void bubble_down(priority_queue *q, int p) {
			int c = pq_young_child(p);
			int min_index = p;
			for (int i = 0; i <= 1; i++) { // 두 자식과 비교
			if ((c + i) <= q->n) {
			if (q->q[min_index] > q->q[c + i]) {
			min_index = c + i;
			}
			}
			}
			if (min_index != p) {
			pq_swap(q, p, min_index);
			bubble_down(q, min_index);
			}
			}
			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>
			<syntaxhighlight lang="c">

			</syntaxhighlight>

	==Applications of Priority Queues==		==Applications of Priority Queues==

Pinkgo: /* Array-Based Heaps */

2025-09-20T09:13:15Z

Array-Based Heaps

← 이전 판		2025년 9월 20일 (토) 09:13 판
34번째 줄:		34번째 줄:

	이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.		이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.

			==Implementing Heap==

	==Applications of Priority Queues==		==Applications of Priority Queues==

Pinkgo: /* Heap */

2025-09-20T09:11:55Z

Heap

← 이전 판		2025년 9월 20일 (토) 09:11 판
28번째 줄:		28번째 줄:

	===Array-Based Heaps===		===Array-Based Heaps===
			일반적으로 트리는 각 노드가 자식 포인터를 가지지만, 힙은 배열 기반 표현이 더 자연스럽다. 배열 인덱스를 통해 binary tree를 나타내기 위해서는 아래와 같은 규칙을 가지면 된다:
			# 노드 k의 왼쪽 자식: 2k
			# 오른쪽 자식: 2k+1
			# 부모: ⌊k/2⌋

			이때 트리가 희소(sparse) 하면 비효율적이다. 예를 들어, 높이 h를 가지는 트리에 대해 <math>n < 2^h</math>일 때, 존재하지 않는 내부 노드도 배열 공간을 차지한다. 따라서 트리가 perfect balanced tree라는 것은 주어진 노드 수에 대해 높이 h가 최소라는 것을 의미하므로, 주어진 노드 수에 대해 배열을 최대한 활용할 수 있다. 또한 배열 기반의 표현은 포인터 기반 트리보다 수정 유연성이 떨어진다.

	==Applications of Priority Queues==		==Applications of Priority Queues==

Pinkgo: /* Heap */

2025-09-19T21:32:51Z

Heap

← 이전 판		2025년 9월 19일 (금) 21:32 판
25번째 줄:		25번째 줄:
	# 마지막 레벨은 노드 들이 왼쪽부터 순서대로 채워지고, 그 위 레벨들은 전부 채워져야 한다.		# 마지막 레벨은 노드 들이 왼쪽부터 순서대로 채워지고, 그 위 레벨들은 전부 채워져야 한다.
	# 루트의 키는 자식들의 키보다 작거나 같아야 하며(min heap의 경우), 모든 서브트리도 다시 힙 구조여야 한다.		# 루트의 키는 자식들의 키보다 작거나 같아야 하며(min heap의 경우), 모든 서브트리도 다시 힙 구조여야 한다.
	조건 1, 2는 트리의 형태(shape) 를, 조건 3은 순서 규칙(ordering) 을 규정한다.		조건 1, 2는 트리의 형태(shape) 를, 조건 3은 순서 규칙(ordering) 을 규정한다. Figure 1은 각각 트리 구조와 배열 인덱스를 통해 표현한 힙 자료구조의 예시이다. 힙은 이러한 조건을 통해서 partial order를 유지한다. 이는 전체를 정렬하지 않아도 최솟값/최댓값을 빠르게 식별 가능하게 한다.

			===Array-Based Heaps===

	==Applications of Priority Queues==		==Applications of Priority Queues==