Junhyuk Yu

I will be an amazing person.

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

힙은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리(Almost Complete Tree)인 특수한 트리 기반의 자료 구조이다.

힙은 항상 균형을 유지하는 특징 때문에 다양한 분야에서 널리 활용된다. 우선순위 큐, 다익스트라 알고리즘, 힙 정렬과 최소 신장 트리를 구현하는 프림 알고리즘 등에 활용되며, 중앙값의 근사값을 빠르게 구하는 데도 활용할 수 있다.

힙 연산

파이썬의 heapq 모듈에서 지원하는 최소 힙 연산을 파이썬의 리스트로만 동일하게 구현해보자.

Class BinaryHeap(object):
	def __init__(self):
		self.items = [None]
	
	def __len__(self):
		return len(self.items) - 1

인덱스 계산을 깔끔하게 하기 위해, 0번 인덱스는 사용하지 않게 None으로 미리 설정을 해두었다.

삽입

힙에 요소를 삽입하기 위해서는 업힙 연산을 수행해야 한다. percolate_up()이라는 함수로 정의를 해보자. 힙에 요소를 삽입 과정은 다음과 같다.

  1. 요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입(배열로 표현할 경우 가장 마지막에 삽입)
  2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경
  3. 계속해서 부모값과 비교해 위치를 변경(가장 작은 값일 경우 루트까지 올라감)

이 과정을 코드로 구현해보자.

def _percolate_up(self):
	i = len(self)
	parent = i // 2
	while parent > 0:
		if self.items[i] < self.items[parent]:
			self.items[i], self.items[parent] = self.items[parent], self.items[i]
			i = parent
			parent = i // 2

def insert(self):
	self.items.append(k)
	self._percolate_up()

추출

추출 자체는 매우 간단하다. 루트를 추출하면 된다. 추출 이후에 비어있는 루트에는 가장 마지막 요소가 올라가게 되고 이번에는 반대로 자식 노드와 값을 비교해서 자식보다 크면 내려가는 다운힙 연산이 수행된다.

def _percolate_down(self, idx):
	left = idx * 2
	right = idx * 2 + 1
	smallest = idx

	if left <= len(self) and self.items[smallest]:
		smallest = left

	if right <= lent(self) and self.items[smallest]:
		smallest = right

	if smallest != idx:
		self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
	self._percolate_down(smallest)

def extract(self):
	extracted = self.items[1]
	self.items[1] = self.items[len(self)]
	self.items.pop()
	self._percolate_down(1)
	return extracted

기존 파이썬 heap 모듈의 heaqp.heappush()는 insert()에, heapq.heappop()은 extract()에 대응된다.

배열의 k번째 큰 요소

정렬되지 않은 배열에서 k번째 큰 요소를 추출하라.

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
  • 풀이: heapq모듈 이용
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = list()
        for n in nums:
            heapq.heappush(heap, -n)

        for _ in range(1, k):
            heapq.heappop(heap)

        return -heapq.heappop(heap)
  • 풀이: heapq 모듈의 heapify 이용

heapify()란 주어진 자료구자고 힙 특성을 만족하도록 바꿔주는 연산이다.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)

        for _ in reange(len(nums) - k):
            heapq.heappop(nums)

        return heapq.heappop(nums)
  • 풀이: heapq 모듈의 nlargest 이용
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다. 마지막 인덱스만 필요하기 때문에 [-1] 처리를 해준다.

  • 정렬을 이용한 풀이
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums, reverse = True)[k-1]

You may also enjoy