자료구조/알고리즘 - 힙

힙?

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가기때문에 최대의 값들을 빠르게 구할 수 있다.

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

힙은 최댓값을 가장 위로 올릴 수도있고 최솟값을 가장 위로 올릴 수도 있습니다.

class BinanryMaxHeap:
    def __init__(self):
        self.item = [None]

    def __len__(self):
        return len(self.item)-1

    def percolate_up(self):
        cur = len(self)
        parent = cur // 2

        while parent > 0:
            if self.item[cur] > self.item[parent]:
                self.item[cur], self.item[parent] = self.item[parent], self.item[cur]

            cur = parent
            parent = cur//2

    def percolate_down(self, cur):
        big = cur
        left = cur * 2
        right = cur * 2 + 1

        if left <= len(self) and self.item[big] < self.item[left]:
            big = left
        if right <= len(self) and self.item[big] < self.item[right]:
            big = right

        if cur != big:
            self.item[cur], self.item[big] = self.item[big], self.item[cur]
            self.percolate_down(big)

    def insert(self, k):
        self.item.append(k)
        self.percolate_up()

    def extract(self):
        if len(self) < 1:
            return None
        root = self.item
        self.item[1] = self.item[-1]
        self.item.pop()
        self.percolate_down(1)
        return root

힙을 구현하는 코드이다.

heapq 모듈

파이썬에서는 heapq라는 모듈을 제공합니다.
heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공합니다.

heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다. 자바의 PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야 합니다. (추가, 삭제 시 O(logN)의 시간 복잡도를 가짐)

그렇게 때문에, 그냥 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 합니다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙입니다.

힙 선언과 추가

import heapq

heap = []

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)

# heap = [1, 3, 7, 4]
# heap[0] = 최소 값

힙 원소 삭제

print(heapq.heappop(heap))
print(heap)

# 1
# [3, 4, 7]

기존 리스트 힙으로 변환

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)

#[1, 3, 5, 4, 8, 7]

최대 힙

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1

 

heapq.nlargest(n, iterable, key=None)

iterable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환하는 함수

heapq.nsmallest(n, iterable, key=None)

iterable에 의해 정의된 데이터 집합에서 n 개의 가장 작은 요소로 구성된 리스트를 반환하는 함수

import heapq

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heapq.nlargest(2,heap))
print(heapq.nsmallest(2,heap))

#[8, 7]
#[1, 3]

오늘푼 문제

https://geonoo.tistory.com/111

[파이썬] 1464. Maximum Product of Two Elements in an Array - 리트코드

https://geonoo.tistory.com/112

[파이썬] 1337. The K Weakest Rows in a Matrix - 리트코드

https://geonoo.tistory.com/113

[파이썬] 215. Kth Largest Element in an Array - 리트코드

https://geonoo.tistory.com/114

[파이썬] 백준 - 최소 힙 - 1927

회고

오늘만큼 수월하게 풀린적이 없었 던 것 같다. 물론 쉬운문제 였지만 나름 잘 풀리고 그래서 기분이 좋았다.

처음으로 정식으로 두명씩 짝을 지어서 알고리즘 문제를 풀어봤는데, 다시 코드를 설명하면서 도움도 됐다.
그리고 하루하루 짝이 바뀌어서 내가 배울 수 있는 사람한태는 배우면서 코딩한다는게 좋은 습관 인 것 같다.

하루가 잘풀려서 TIL도 이렇게 일찍쓰게 되었다. 알고리즘 2주차도 벌써 끝나가고 있다.
주특기 공부는 어떤 방식으로 진행 될 지 궁금하면서도 지금은 지금 놓인 일에 최선을 다 할 뿐이다.