doi

doing something

5 minute read


최대 힙/최소 힙의 정의

최대 힙

이진 트리에서, 각 노드의 키 값이 그 자식 노드보다 큰 트리를 최대 트리라고 한다. 최대 힙이란, 최대 트리이면서 완전 이진 트리인 트리를 가리킨다. 반드시 두 조건을 동시에 만족해야 한다.

단, 이때 같은 레벨에 위치하는 노드들의 대소 관계는 비교하지 않아도 된다. 예시로, 아래와 같은 형태의 트리도 최대 힙이라고 할 수 있다.

# 2번 노드에 2가, 3번 노드에 8이 위치하지만 최대 힙이 맞다.
      1
     / \
    2   8
   / \
  4   5

항상 루트에 최대값이 존재하기 때문에, 최대 값의 탐색에 유용하다. 또한 내림차순 정렬에 유용하게 사용된다.

최소 힙

위와 동일하게, 최소 트리이면서 완전 이진 트리인 트리를 가리킨다.

항상 루트에 최소값이 존재하기 때문에, 최소 값의 탐색과 오름차순 정렬에 유용하게 사용된다.

파이썬의 heapq는 기본적으로 최소 힙만을 제공한다.


최대 힙/최소 힙에 노드 추가하기

최대/최소 트리이면서 완전 이진 트리여야 한다는 조건을 유지하기 위해, 아래의 두 가지 규칙에 따라 노드를 추가한다.

  1. 새 노드는 트리의 마지막 위치에 삽입한다.
  2. 알맞은 위치를 찾을 때까지, 해당 노드의 부모 노드와 반복적으로 비교해 나간다. (이때, 동 레벨에 위치한 노드들과의 대소는 비교하지 않음에 주의한다.)

아래는 최대 힙에 8이라는 키 값을 가진 새 노드를 추가하는 과정이다.

# 초기 최대 힙
      9
     / \
    7   6
   / \
  5   3

# 새 노드 8 삽입 (완전 이진 트리 유지)
      9
     / \
    7   6
   / \   \
  5   3   8

# 부모 노드인 6과 비교했을 때 8이 더 크므로, 위치 변경
      9
     / \
    7   8   ← 8이 위로 올라감
   / \   \
  5   3   6

최대 힙/최소 힙에서 노드 추가에 필요한 시간은, 상위 노드와 대소를 비교하여 힙을 재구성하는 횟수와 같다. 이는 트리의 높이(log₂n)에 비례하므로, 시간 복잡도는 O(log₂n)이다.


최대 힙/최소 힙에서 노드 삭제하기

힙에서의 노드 삭제는, 일반적으로 최대 값/최소 값인 루트 노드의 삭제를 의미한다. 노드를 삭제할 때 역시 노드를 추가할 때와 마찬가지로 최대/최소 트리이면서 완전 이진 트리여야 한다는 조건을 유지하기 위해, 규칙에 따라 노드를 삭제한다.

최대 힙에서 노드 삭제

  1. 루트 값(최대값)을 반환할 변수에 복사한 뒤, 마지막 위치의 노드를 루트로 이동시킨다. (완전 이진 트리 조건을 위함)
  2. 루트의 좌우 자식 노드 중, 큰 값을 가진 자식 노드를 비교 대상으로 선택한다.
  3. 루트와 선택한 자식 노드의 값을 비교해, 루트가 더 크다면 종료한다. 선택한 자식 노드가 더 크다면 둘의 위치를 교환한다.
  4. 하위 레벨에서 2~4의 과정을 반복한다.

최소 힙에서 노드 삭제

  1. 루트 값(최소값)을 반환할 변수에 복사한 뒤, 마지막 위치의 노드를 루트로 이동시킨다. (완전 이진 트리 조건을 위함)
  2. 루트의 좌우 자식 노드 중, 작은 값을 가진 자식 노드를 비교 대상으로 선택한다.
  3. 루트와 선택한 자식 노드의 값을 비교해, 루트가 더 작다면 종료한다. 선택한 자식 노드가 더 작다면 둘의 위치를 교환한다.
  4. 하위 레벨에서 2~4의 과정을 반복한다.

아래는 최소 힙에서 노드를 삭제하는 과정이다.

# 초기 최소 힙
      1
     / \
    3   6
   / \
  5   9

# 루트 노드 1을 변수에 담은 뒤 삭제하고, 마지막 노드 9를 루트로 이동시킴
      9
     / \
    3   6
   / 
  5

# 루트 좌우 자식 노드 3, 6 중 더 작은 값인 3과 9를 비교 -> 3이 더 작으므로 위치 변경
      3
     / \
    9   6
   / 
  5

# 9의 자식 노드 5와 9를 비교 -> 5가 더 작으므로 위치 변경
      3
     / \
    5   6
   / 
  9

노드 삭제의 시간 복잡도 역시 상위 노드와 대소를 비교하여 힙을 재구성하는 횟수와 같다. 따라서 시간 복잡도는 O(log₂n)이다.


파이썬 코드로 구현하기

최대 힙/최소 힙은 이진 트리 특성을 만족하므로, 연결 리스트보다 배열로 구현하는 것이 효율적이다.

아래는 최대 힙에서 노드를 추가하고 삭제하는 기능을 수행하는 파이썬 코드이다. 최대 힙에 원소를 하나씩 추가한 뒤, 모든 원소의 추가가 끝나면 최대 힙을 재구성하면서 루트를 삭제하는 과정을 반복한다. 결과적으로 큰 수부터 내림차순으로 출력된다. 최대 힙의 첫 번째 위치(인덱스 [0]은 사용하지 않으므로, 항상 None으로 표시한다.)

class Heap:
	def __init__(self, size):
		self.size = size
		self.heap = [None] * size # 배열로 구현
		self.count = 0

	def __str__(self):
		return "Heap, 0 is Dummy"

	def add_heap(self, item):
		# 원소의 추가가 끝났다면 리턴
		if self.isFull():
			return
			
		self.count += 1
		i = self.count

		# i가 루트가 아니면서 새로 추가되는 노드(item)이 부모 노드보다 큰 동안
		while i != 1 and item > self.heap[i // 2]:
			# 한 레벨씩 위로 올라가며 부모 노드와 비교
			self.heap[i] = self.heap[i // 2]	
			i //= 2		
			
		# 비교가 끝나면 해당 위치에 item을 추가
		self.heap[i] = item
		
		print("%2d" % item, end = ' ')
		print(self.heap)

	def isFull(self):
		# 모든 원소의 추가가 끝남
		return self.size - 1 == self.count

	def del_heap(self):
		if self.count == 0:
			print("Empty heap")
			return
			
		item = self.heap[1] # 루트 노드를 item에 담음
		temp = self.heap[self.count] # 마지막 노드를 temp에 담음
		self.heap[self.count] = None # 마지막 노드 삭제
		self.count -= 1 # 마지막 노드의 위치 -1
		
		parent = 1 # 루트 노드에서 시작
		child = 2 # 루트 노드의 왼쪽 자식 노드
		
		# 자식 노드 인덱스 <= 마지막 노드 인덱스일 동안
		while child <= self.count: 
			# 자식 노드의 인덱스가 마지막 노드의 인덱스보다 작으면서 
			# 왼쪽 자식 노드가 오른쪽 자식 노드보다 작다면
			if child < self.count and self.heap[child] < self.heap[child + 1]: 
				child += 1 # 비교 대상을 오른쪽 노드로 변경
			if temp >= self.heap[child]:
				break # 마지막 노드가 비교 대상 자식 노드보다 크다면 비교 종료
				
			self.heap[parent] = self.heap[child] # 부모와 자식 교환
			parent = child # 레벨을 한 단계 내림
			child *= 2 # 새로운 자식 노드
			
		if self.count != 0:
			self.heap[parent] = temp # 마지막 위치에 temp를 담음
			
		return item # 루트 노드였던 값을 반환함

h = Heap(10)
num = [10, 20, 5, 12, 40, 80]
print(h)
print("Insert into Heap", end = "\n")
for i in num:
	h.add_heap(i)
print("Count =", h.count)
print("Delete from Heap", end="\n")
for i in range (h.count):
	print(h.heap)
	print(h.del_heap(), end = ' =>')
print(h.heap)


우선순위 큐

우선 순위 큐(Priority Queue)란, 큐에 대기 중인 작업을 도착 순서(선입 선출, FCFS)가 아니라 작업의 우선 순위에 따라 처리하는 큐를 말한다. 우선 순위 큐는 운영 체제의 스케줄링, 은행 고객 서비스 등 다양한 분야에서 활용된다. 우선 순위를 정하는 기준은 적용하는 분야의 특성에 맞게 달라질 수 있다.

우선 순위 큐를 구현하는 방법에는 여러 가지가 있다.

  1. 비정렬 선형 리스트(unsorted list): 리스트에 작업을 추가할 때는 우선 순위를 고려하지 않고 도착 시간대로 가장 뒤에 추가한다. 그러나 리스트에서 삭제할 때는 우선 순위가 높은 작업부터 삭제한다. 작업 추가에 대한 시간 복잡도는 O(1), 삭제에 대한 시간 복잡도는 원소의 개수에 비례하여 O(n)이다.
  2. 정렬 선형 리스트(sorted list): 큐에 작업을 추가할 때 우선 순위를 고려해 작업을 정렬한다. 삭제할 때는 정렬 없이 바로 제거된다. 비정렬 선형 리스트와 반대로, 작업 추가의 시간 복잡도가 O(n), 삭제의 시간 복잡도가 O(1)이다.
  3. 최대 힙: 작업들을 원소로 삼아 최대 힙을 구성하면 우선 순위가 가장 높은 작업이 항상 루트에 놓이게 된다. 루트를 큐에서 삭제할 때마다 힙을 재구성하는 작업을 수행한다. 따라서 작업의 추가와 삭제에 걸리는 시간은 O(log₂n)이다.


참고 도서: 파이썬으로 배우는 자료구조 프로그래밍, 유석종 저

You may also enjoy