[항해99] Heap 힙

힙?

힙합이 아닙니다

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 입니다

- 출처 위키백과

 

삐뚤어 보인다면,, 맞게 보신겁니다.

 

힙구조를 한번 봅시다.

힙은 기본적으로 완전이진트리 입니다.

자식노드는 왼쪽노드부터 차곡차곡 빠진 노드 없이 쌓아간다는게 특징이지요.

 

그렇지만 이진탐색트리와는 차이가 있습니다.

힙은 부모노드가 자식노드보다 크거나 (max heap), 작아야한다(min heap)라는 규칙이 있지만, 왼쪽 자식과 오른쪽 자식간의 차이는 없습니다.

그러나 이진 탐색트리는 부모노드의 값보다 작은 값을 가지면 왼쪽 자식, 큰 값을 가지면 오른쪽 자식으로 가기 떄문에 힙과는 사용에서 차이가 있습니다.

 

힙의 삽입

힙의 삽입은 간단합니다. 맨 마지막 노드 다음에 값을 넣으면 되거든요.

그 뒤에, 넣은 노드의 부모와 자신을 비교해서 자식노드가 크다면 ( 최대힙의 경우) 부모노드와 자식노드의 위치를 바꿔줍니다. 이 과정을 루트노드까지 반복해주면 삽입이 완료됩니다.

힙의 삭제

힙은 제일 첫 원소만 삭제할 수 있습니다. 루트 노드를 삭제하는 법을 알아보면,

제일 먼저 루트노드와 마지막 노드의 자리를 바꾼다 ( 마지막 노드가 루트노드가 됨 ) 

그 이후 루트노드에서 양쪽 자식 중에 큰 값 (최

대힙의 경우)과 자신의 위치를 바꾸는 과정을 리프노드까지 반복합니다.

자신과 마지막 노드를 바꾼다

양쪽 노드 중에 큰 노드와 바꾼다

반복..

결과

힙의 원소 삭제는 트리의 높이 만큼의 시간복잡도를 가지니

O(log N)이라고 할 수 있습니다.

Maximum Product of Two Elements in an Array 배열의 최대 곱

https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array

Maximum Product of Two Elements in an Array - LeetCode

list에서 제공하는 sort기능을 쓸 수도 있지만, 힙을 연습하는 의미로 풀어보았습니다.

파이썬 heapq에서 제공하는 함수를 써보는 연습을 하도록 합시다.

import heapq
from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:

        heapq.heapify(nums)
        lst = heapq.nlargest(2,nums)

        return (lst[0] -1) * (lst[1]-1)

행렬에서 제일 작은 k개 행 찾기

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

The K Weakest Rows in a Matrix - LeetCode

마찬가지로 리스트로도 풀 수 있는 문제지만, 힙 쓰는 연습을 해보는 문제.

from typing import List
import heapq


class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        heap = []

        for i in range(len(mat)):
            cnt = mat[i].count(1)
            heapq.heappush(heap, (cnt, i))

        return [heapq.heappop(heap)[1] for i in range(k)]

배열에서 K번째로 큰 원소

https://leetcode.com/problems/kth-largest-element-in-an-array/

Kth Largest Element in an Array - LeetCode

sort를 하지않고 배열에서 k번째로 큰 원소를 구하는 문제. 

힙은 처음부터 큰 순서대로 ( 또는 작은 순서대로 ) 정리되어서 들어가기 때문에, k번째로 큰 원소는 힙의 원소를 k번 뽑았을 때 리턴값이 될 것.

*참고로 힙을 구현해서 풀어보았습니다. 파이썬 heapq이용하면 간단하게 풀 수 있음! 후술하겠지만, 파이썬 힙은 minheap이라 거꾸로 구성해줘야 합니다.

from typing import List

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

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

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

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

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

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

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        maxheap = BinaryMaxHeap()

        for elem in nums:
            maxheap.insert(elem)
            
        return [maxheap.extract() for _ in range(k)][k-1]

최소힙

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

수많은 시간초과

2023.12.22 - [TIL/[순간순간 알게된 짧은 지식] TIL] - 파이썬 입출력 시간

파이썬 입출력 시간

완료  시간 관련 게시글은 이후에 따로 정리해서 올리도록 하겠습니다 

 

파이썬 heapq를 그대로 이용해서 입출력만 빠르게 하면 되는 문제.

import heapq
import sys

heap = []

n = int(sys.stdin.readline().rstrip())

for _ in range(n):
    i = int(sys.stdin.readline().rstrip())
    if i == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, i)

최대힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

파이썬에서는 최소힙을 제공하므로, 넣는 데이터의 부호를 바꾸어주면 최대값이 최소값이 된다.

출력할 때는 다시 부호를 바꾸어서 출력.