[프로그래머스 강의] 23강 힙(Heaps)(2)

힙(Heaps)

 

힙(Heap) 이란 ?

완전 이진 트리(Complete Binary Tree)로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다.

 

---

최대 힙(Max heap) 원소 삭제

1. 루트 노드 제거:

→ Max heap의 경우 최대 값 제거 

→ Min heap의 경우 최소 값 제거

 

2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치

 

3. 자식 노드들 과의 값 비교 하며 아래로 이동 

→ 자식 노드들 중 더 큰 값 기준으로 이동 

 

 

---

최대 힙(Max heap) 원소 삭제 - 시간 복잡도

원소의 개수가 N 인 최대 힙(Max heap)에서 최대 값 삭제

→  자식 노드 들과의 대소 비교 최대 횟수: 2(왼쪽 노드 오른쪽 노드 비교) x log n(트리 높이)

 

최악의 경우 시간 복잡도 O(log n)의 삭제 연산 

 

---

문1. 최대 힙(Max heap) 원소 삭제

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = 2*i

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = 2*i +1​
        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[smallest]​ and self.data[left] > self.data[right]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[smallest] and self.data[right] > self.data[left]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[smallest], self.data[i] = self.data[i], self.data[smallest]​
            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0

---

최대/최소 힙 응용

1. 우선순위 큐(Priority Queue)

큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In First Out, FIFO) 구조의 자료구조이다. 

우선순위 큐(Priority Queue)란 큐와 이름은 비슷하나 동작방식이 다르다. 우선순위 큐의 각 원소는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다.

 

우선순위의 구현은 힙(Heap) 이나 배열 또는 연결리스트로 구현한다. 

 

 ✔ 힙(Heap) 으로 구현 - "느슨한 정렬(반 정렬)"

→  "느슨한 정렬" 상태를 유지하며 Enqueue :

        O(logn) 의 시간 복잡도

→  Enqueue  하는 원소들을 최대 힙 또는 최소 힙에 삽입 시 우선 순위에 따라 순서대로 Dequeue : 

       최대 값 또는 최소 값을 순서대로 추출하며 O(logn) 의 시간 복잡도

 

2. 힙 정렬(Heap sort)

→ 정렬 되지 않은 원소들을 아무 순서로나 최대 힙 또는 최소 힙에 삽입:

      시간 복잡도 O(logn)

→ 삽입이 끝나면 힙이 비게 될 때까지 원소를 하나 씩 삭제:

     시간 복잡도 O(logn)

→ 원소들이 삭제 된 순서가 원소들의 정렬 순서

→ 힙 정렬 알고리즘의 시간 복잡도 O(nlogn)

 n 개의 노드에 대해 각각 삽입(logn), 삭제(logn) 연산을 해주기 때문에 O(nlogn)의 시간 복잡도를 갖게 된다.

 

2-1. 힙 정렬 코드 구현 

 

* 파이썬 모듈 heapq 이용

import heapq

 

import heapq

def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, value)
    for i in range(len(heap)):
        result.append(heapq.heappop(heap))
    return result

result = heapsort([1,9,0,7,8,6,3,5])
print(result)

# result
[0, 1, 3, 5, 6, 7, 8, 9] # 오름차순 정렬

 

def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, -value)
    # print(heap)
    # [-9, -8, -6, -5, -7, 0, -3, -1]
    for i in range(len(heap)):
        result.append(-heapq.heappop(heap))
    return result

result = heapsort([1,9,0,7,8,6,3,5])
print(result)

# result
[9, 8, 7, 6, 5, 3, 1, 0] # 내림차순 정렬

 

 

* 참고

[프로그래머스 강의] 16강 우선순위 큐