22강 요약

힙이랑 무엇인지, 또 어떻게 정렬되는지, 실제로 데이터를 삽입하고 힙을 유지시키기 위해 정렬 해봄

22강 내용

힙이란?

이진 트리의 한 종류
1. 루트(root)노드가 언제나 최댓값 또는 최솟값을 가짐
-최대 힙(max heap), 최소 힙(min heap)
2. 완전 이진 트리 여야 함

배열로 트리를 표현

힙은 항상 완전 이진 트리 여야 하므로 배열을 사용하면 편리하게 구현할수 있습니다. 완전 이진 트리는 낮은 레벨부터, 그리고 왼쪽 부터 순서대로 저장되므로 저장공간이 연속될 수 있습니다. 즉 배열로 용이하게 표현 가능 합니다.

원소 삽입

insert(self,itme) - 원소를 삽입
원소 삽입 이후에도 힙을 유지하기 위해 정렬이 필요 합니다.

1. 마지막에 새로운 원소를 삽입
2. 부모노드와 값을 비교 후 크다면 부모노드와 치환

def insert(self, item):
        m = len(self.data)
        self.data.append(item)
        
        if m == 1: #빈 리스트일때 0은 None이므로 에러
            return
        
        while self.data[m//2] < self.data[m]: #값이 클때 까지
            self.data[m], self.data[m//2] = self.data[m//2], self.data[m] #치환
            m = m // 2 #상위 레벨로
            if m == 1: #루트노드면 종료
                break

문제

class MaxHeap:

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


    def insert(self, item):
        m = len(self.data)
        self.data.append(item)
        
        if m == 1: #빈 리스트일때 0은 None이므로 에러
            return
        
        while self.data[m//2] < self.data[m]: #값이 클때 까지
            self.data[m], self.data[m//2] = self.data[m//2], self.data[m] #치환
            m = m // 2 #상위 레벨로
            if m == 1: #루트노드면 종료
                break

def solution(x):
    return 0

23강 요약

힙내 원소 삭제 후 정렬

23강 내용

힙의 삭제는 항상 루트노드를 삭제합니다. 하지만 완전이진트리를 유지해야 하므로 마지막 노드와 치환하고 정렬하는 등의 과정이 뒤따릅니다.

root노드 삭제와 마지막 노드와 치환

remove(self) - 루트노드를 삭제 하고 치환합니다.

	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

len(self.data)로 트리가 비어있는지 여부를 확인합니다. 비어있지 않다면, 루트노드와 마지막 노드를 치환후 마지막 노드를 삭제합니다. 그리고 maxHeapify()를 호출하여 힙을 정렬합니다.

힙을 정렬

삭제와 치환과정에서 루트노드 다음으로 가장 큰 노드가 마지막 노드면 상관이 없지만 아니라면 힙을 유지할 수 없습니다. 따라서 정렬하는 과정이 필요합니다. 삽입과 반대로 루트부트 말단노드방향으로 자식의 크기와 자신을 비교합니다.

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

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1

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

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

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)

left자식과 right 자식, 두자식 중 나머지 한자식과 본인보다 큰 자식이 있다면 치환합니다. 이때 존재여부도 확인하여야 하는데 객체와 링크를 사용하는 트리와 달리 배열을 사용하므로 len(self.data)로 크기를 벗어나는지 확인하면 존재여부를 확인할 수 있습니다.

문제

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 = i * 2

        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1

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

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

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/22%2C23%EA%B0%95/22%2C23%EA%B0%95.py