TIL_38 : 힙

JaHyeon Gu·2021년 9월 30일
0

자료 구조

목록 보기
8/12
post-thumbnail

🙄 힙


➡ 힙이란?

  • 아래 두 개의 조건을 만족하는 트리
    1. 형태 속성 : 힙은 완전 이진 트리다 : 노드의 개수가 nn개일 때 높이는 O(lg(n))O(lg(n))
    2. 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다

➡ 힙 만들기_1 (Heapify)

  • 힙 속성을 지키지 않는 노드가 있을 때, 그 노드가 맞는 위치를 찾을 때까지 재배치
  • 부모, 자식 노드들을 비교해서 가장 큰 노드가 부모 노드가 아니라면 자리를 바꿔준다

시간 복잡도

  • 노드의 개수를 nn이라고 할 때
  • 최악의 경우는 root nodeleaf node까지 가는 경우
  • 최악의 경우 트리의 높이만큼 데이터를 비교하고 재배치
  • 높이는 O(lg(n))O(lg(n)), 따라서 시간 복잡도 : O(lg(n))O(lg(n))
def swap(tree, index_1, index_2):
    """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
    temp = tree[index_1]
    tree[index_1] = tree[index_2]
    tree[index_2] = temp


def heapify(tree, index, tree_size):
    """heapify 함수"""

    # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산
    left_child_index = 2 * index
    right_child_index = 2 * index + 1

    if left_child_index < tree_size and right_child_index < tree_size:
        top_of_fam = max(tree[index], tree[left_child_index], tree[right_child_index])
        if top_of_fam is tree[left_child_index]:
            swap(tree, index, left_child_index)
            heapify(tree, left_child_index, tree_size)
        elif top_of_fam is tree[right_child_index]:
            swap(tree, index, right_child_index)
            heapify(tree, right_child_index, tree_size)
        

# 실행 코드
tree = [None, 15, 5, 12, 14, 9, 10, 6, 2, 11, 1]  # heapify하려고 하는 완전 이진 트리
heapify(tree, 2, len(tree))  # 노드 2에 heapify 호출
print(tree) 

# [None, 15, 14, 12, 11, 9, 10, 6, 2, 5, 1]

➡ 힙 만들기_2

  • leaf node부터 heapify에 대입
  • root nodeheapify를 호출할 차례, 밑에 모든 노드들은 힙 속성을 지키고 있음

시간 복잡도

  • 특정 노드에 heapify를 호출하는 건 O(lg(n))O(lg(n))
  • 힙을 만들려면 heapifynn개의 노드에 모두 호출
  • 시간 복잡도 : O(nlg(n))O(nlg(n))

➡ 힙 정렬

  1. 힙을 만든다 (2번 방법으로 leaf node부터 heapify)
  2. root node와 마지막 노드를 바꿔준다
  3. 바꾼 노드는 없는 노드 취급한다
  4. 새로운 노드가 힙 속성을 지킬 수 있게 heapify 호출
  5. 모든 인덱스를 돌 때까지 2~4단계 반복

👉 내림 차순으로 정렬하고 싶다면???
👉 힙 속성을 반대로 바꾸고 똑같은 알고리즘을 적용하면 된다
👉 부모 노드의 데이터가 자식 노드의 데이터보다 작아야 된다고 바꾸면 됨

def swap(tree, index_1, index_2):
    """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
    temp = tree[index_1]
    tree[index_1] = tree[index_2]
    tree[index_2] = temp


def heapify(tree, index, tree_size):
    """heapify 함수"""

    # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산
    left_child_index = 2 * index
    right_child_index = 2 * index + 1

    largest = index  # 일단 부모 노드의 값이 가장 크다고 설정

    # 왼쪽 자식 노드의 값과 비교
    if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
        largest = left_child_index

    # 오른쪽 자식 노드의 값과 비교
    if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
        largest = right_child_index
    
    if largest != index: # 부모 노드의 값이 자식 노드의 값보다 작으면
        swap(tree, index, largest)  # 부모 노드와 최댓값을 가진 자식 노드의 위치를 바꿔준다
        heapify(tree, largest, tree_size)  # 자리가 바뀌어 자식 노드가 된 기존의 부모 노드를대상으로 또 heapify 함수를 호출한다

def heapsort(tree):
    """힙 정렬 함수"""
    tree_size = len(tree)

    for i in range(tree_size,0,-1):
        heapify(tree, i, tree_size)
    for j in range(tree_size-1,0,-1):
        swap(tree, 1, j)
        heapify(tree, 1, j)

# 실행 코드
data_to_sort = [None, 6, 1, 4, 7, 10, 3, 8, 5, 1, 5, 7, 4, 2, 1]
heapsort(data_to_sort)
print(data_to_sort)

# [None, 1, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 10]

➡ 힙 정렬 시간 복잡도

  1. 먼저 리스트를 힙으로 만듦
  2. root 노드와 마지막 노드의 위치를 바꾸고 마지막 노드는 힙에서 없다고 가정
  3. 새로운 root 노드가 힙 속성을 지킬 수 있게 heapify
  4. 힙에 남아있는 노드가 없도록 단계 2 ~ 3을 반복
  1. O(nlg(n))O(nlg(n))
  2. ~ 4. O(nlg(n))O(nlg(n))

O(2nlg(n))O(2nlg(n)) = O(nlg(n))O(nlg(n))

정렬 알고리즘시간 복잡도
선택 정렬O(n2)O(n^2)
삽입 정렬O(n2)O(n^2)
합병 정렬O(nlg(n))O(nlg(n))
퀵 정렬평균 O(nlg(n))O(nlg(n)) 최악 O(n2)O(n^2)
힙 정렬O(nlg(n))O(nlg(n))

👉 힙 정렬은 선택 정렬과 삽입 정렬보다는 좋고, 합병 정렬과 퀵 정렬과는 비슷한 성능



🙄 우선순위 큐


➡ 우선순위 큐란?

  • 큐나 스택처럼 추상 자료형
  • 큐는 먼저 들어간 데이터가 먼저 나오는 자료형
  • 우선순위 큐는 각 데이터에 우선순위가 있고 우선순위가 높은 데이터가 먼저 나오는 구조
  • 힙을 이용하면 우선순위 큐를 효율적으로 구현할 수 있음

➡ 힙에 데이터 삽입하기

  • 힙의 마지막 인덱스에 데이터를 삽입
  • 삽입한 데이터와 부모 노드의 데이터를 비교
  • 부모 노드의 데이터가 더 작으면 둘의 위치를 바꿔줌
  • 새로 삽입한 노드가 제 위치를 찾을 때까지 부모 노드와의 비교 반복
def swap(tree, index_1, index_2):
    """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
    temp = tree[index_1]
    tree[index_1] = tree[index_2]
    tree[index_2] = temp

def reverse_heapify(tree, index):
    """삽입된 노드를 힙 속성을 지키는 위치로 이동시키는 함수"""
    parent_index = index // 2  # 삽입된 노드의 부모 노드의 인덱스 계산
    largest = parent_index
    if 0 < parent_index < len(tree) and tree[parent_index] < tree[index]:
        swap(tree, index, parent_index)
        reverse_heapify(tree, parent_index)
        

class PriorityQueue:
    """힙으로 구현한 우선순위 큐"""
    def __init__(self):
        self.heap = [None]  # 파이썬 리스트로 구현한 힙

    def insert(self, data):
        """삽입 메소드"""
        self.heap.append(data)
        reverse_heapify(self.heap, len(self.heap)-1)
        
    def __str__(self):
        return str(self.heap)


# 실행 코드
priority_queue = PriorityQueue()

priority_queue.insert(6)
priority_queue.insert(9)
priority_queue.insert(1)
priority_queue.insert(3)
priority_queue.insert(10)
priority_queue.insert(11)
priority_queue.insert(13)

print(priority_queue)

# [None, 13, 9, 11, 3, 6, 1, 10]

➡ 힙에서 최고 우선순위 데이터 추출하기

  • root 노드와 미자막 노드를 서로 바꿔 준다
  • 마지막 노드의 데이터를 변수에 저장한다
  • 마지막 노드를 삭제한다
  • root 노드에 heapify를 호출해서 망가진 힙 속성을 고친다
  • 변수에 저장한 데이터를 리턴한다 (최고 우선순위 데이터)
from heapify_code import *

class PriorityQueue:
    """힙으로 구현한 우선순위 큐"""
    def __init__(self):
        self.heap = [None]  # 파이썬 리스트로 구현한 힙

    def insert(self, data):
        """삽입 메소드"""
        self.heap.append(data)  # 힙의 마지막에 데이터 추가
        reverse_heapify(self.heap, len(self.heap)-1) # 삽입된 노드(추가된 데이터)의 위치를 재배치

    def extract_max(self):
        """최우선순위 데이터 추출 메소드"""
        swap(self.heap, 1, len(self.heap)-1)
        max_value = self.heap[-1]
        self.heap.pop()
        heapify(self.heap, 1, len(self.heap))
        return max_value
        
    def __str__(self):
        return str(self.heap)

# 출력 코드
priority_queue = PriorityQueue()

priority_queue.insert(6)
priority_queue.insert(9)
priority_queue.insert(1)
priority_queue.insert(3)
priority_queue.insert(10)
priority_queue.insert(11)
priority_queue.insert(13)

print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())

# 13
# 11
# 10
# 9
# 6
# 3
# 1

➡ 힙 삽입, 추출 시간 복잡도

힙의 삽입 연산 시간 복잡도

  • 힙의 마지막 인덱스에 데이터를 삽입 : O(1)O(1)
  • 부모 노드의 데이터가 더 작으면 둘의 위치를 바꿔줌 : O(lg(n))O(lg(n))

    👉 O(lg(n))O(lg(n))


힙의 추출 연산 시간 복잡도

  • root 노드와 미자막 노드를 서로 바꿔 준다 : O(1)O(1)
  • 마지막 노드의 데이터를 변수에 저장하고 마지막 노드를 삭제한다 : O(1)O(1)
  • root 노드에 heapify를 호출해서 망가진 힙 속성을 고친다 : O(lg(n))O(lg(n))
  • 변수에 저장한 데이터를 리턴한다 (최고 우선순위 데이터) : O(1)O(1)

    👉 O(lg(n))O(lg(n))



🙄 힙으로 구현한 우선순위 큐 평가


  • 우선순위 큐를 구현할 때 힙 말고도 아래 두 자료 구조들을 활용할 수 있다
  1. 정렬된 동적 배열
  2. 정렬된 더블리 링크드 리스트
데이터 삽입데이터 추출
정렬된 동적 배열O(n)O(n)O(1)O(1)
정렬된 더블리 링크드 리스트O(n)O(n)O(1)O(1)
O(lg(n))O(lg(n))O(lg(n))O(lg(n))

👉 정렬된 동적 배열, 더블리 링크드 리스트를 사용하면 데이터를 추출할 때 더 효율적
👉 힙을 사용하면 데이터를 삽입할 때 더 효율적

profile
IWBAGDS

0개의 댓글