힙 (Heaps)

힙(heap)도 이진 트리의 한 종류로 이진 힙(binary heap) 이라고도 한다. 하지만 이진힙은 특별한 조건들을 만족하는 이진 트리이다.

• 루드(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최댓값을 가지면 최대 힙(max heap), 최솟값을 가지면 최소 힙(min heap)이다.
• 완전 이진 트리여야 한다.
• 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대힙이다. (재귀적으로도 정의가 됨)

최대힙(Max Heap)의 예

 

 

 

 

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어있는가? 이진탐색은 그렇지만 힙은 그렇지 않다.
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진탐색트리는 가능, 힙은 불가
3. 부가의 제약 조건은 어떤 것인가? 힙은 이진탐색트리에 비해 완전 이진트리여야한다는 제약조건이 있다.

 

 

 

최대 힙(Max Heap)의 추상적 자료구조

연산의 정의

• __init__() - 빈 최대 힙을 생성
• insert(item) - 새로운 원소를 삽입
• remove() - 최대 원소(root node)를 반환하고 삭제

 

 

 

 

데이터 표현의 설계

배열을 이용한 이진 트리의 표현

class MaxHeap:
    # 빈 힙을 생성
    def __init__(self):
        self.data = [None]

 

 

 

최대 힙에 원소 삽입

트리의 마지막 자리에 새로운 원소를 임시로 저장

부모 노드와 키 값을 비교하여 위로, 위로 이동

트리의 마지막 자리에 새로운 원소를 임시로 저장

부모 노드와 키 값을 비교하여 위로, 위로 이동

 

 

class MaxHeap:
    def insert(self, item):
        # 흰트 - python에서 두 변수의 값 바꾸기
        # a = 3, b = 5
        # a, b  = b, a
        self.data.append(item)
        
        index = len(self.data) -1
    
        while index != 1:
            numOfParentNode = index//2
            print(numOfParentNode)
            
            if self.data[numOfParentNode] < self.data[index]:
                self.data[numOfParentNode], self.data[index] = self.data[index], self.data[numOfParentNode]
                index = numOfParentNode
            else:
                break

 

 

 

 

 

최대 힙에 원소 삽입의 복잡도

원소의 개수가 n인 최대 힙에 새로운 원소 삽입 -> 부모 노드와 대소 비교 최대 회수 : log(2)N

최악 복잡도 O(logN)의 삽입 연산

 

 

 

 

최대 힙에서 원소의 삭제

루트 노드의 제거 - 이것이 원소들 중 최댓값

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

자식 노드들과의 값 비교와 아래로, 아래로 이동 (자식은 둘이 있을 수 있는데 더 큰값을 기준으로 이동한다)

루트 노드가 최대값이므로 루트 노드를 제거한다.

트리의 마지막 자리 노드인 4를 임시로 루트 노드 자리에 배치한다.

자식 노드들과의 값 비교를 통해 아래로 이동한다. 더 큰 키 값을 가지는 자식쪽으로 이동!

 

 

class MaxHeap:

    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):
        # i는 어느 기준으로 바꿀건가
        
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i * 2
        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1
        greatest = i
        
        # 자신(i), 왼쪽자식(left), 오른쪽자식(right) 중 최대를 찾아서 이것의 인덱스를 smallest에 담는다
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[greatest]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            greatest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[greatest]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            greatest = right
            
        # 만약 이 인덱스가 i와 같지 않다면 자식들 중에 나보다 큰 키값을 가진 노드가 발견된 경우
        if greatest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[greatest] = self.data[greatest], self.data[i]
            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(greatest)

 

 

최대 힙으로부터 원소 삭제 복잡도

원소의 개수가 n인 최대 힙에서 최대 원소 삭제는 자식 노드들과의 대소 비교 최대 회수는 2 * log(2)N이다.

최악 복잡도 O(logN)의 삭제 연산

 

 

 

 

 

최대/최소 힙의 응용

1. 우선 순위 큐(priority queue)

• enqueue 할 때 "느슨한 정렬"을 이루고 있도록 함 : O(logN)
• dequeue 할 때 최댓값을 순서대로 추출 : O(logN)
• 제 16강에서의 양방향 연결 리스트 이용 구현과 효율성 비교

 

2. 힙 정렬 (heap sort)

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logN)
• 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(logN)
• 원소들이 삭제된 순서가 원소들의 정렬 순서
• 정렬 알고리즘 복잡도 : O(logN)

 

def heapSort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)
    sorted = []
    d = H.remove()
    while d:
        sorted.append(d)
        d = H.remove()
    return sorted

 

 

 

 

 

전체 코드

class MaxHeap:
    # 빈 힙을 생성
    def __init__(self):
        self.data = [None, 30, 24,12,18,21,8,6,4,2,19]
        
    def insert(self, item):
        # 흰트 - python에서 두 변수의 값 바꾸기
        # a = 3, b = 5
        # a, b  = b, a
        self.data.append(item)
        
        index = len(self.data) -1
    
        while index != 1:
            numOfParentNode = index//2
            print(numOfParentNode)
            
            if self.data[numOfParentNode] < self.data[index]:
                self.data[numOfParentNode], self.data[index] = self.data[index], self.data[numOfParentNode]
                index = numOfParentNode
            else:
                break
                
                
    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):
        # i는 어느 기준으로 바꿀건가
        
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i * 2
        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i * 2 + 1
        greatest = i
        
        # 자신(i), 왼쪽자식(left), 오른쪽자식(right) 중 최대를 찾아서 이것의 인덱스를 smallest에 담는다
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[greatest]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            greatest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[greatest]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            greatest = right
            
        # 만약 이 인덱스가 i와 같지 않다면 자식들 중에 나보다 큰 키값을 가진 노드가 발견된 경우
        if greatest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[greatest] = self.data[greatest], self.data[i]
            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(greatest)
            
            
def heapSort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)
    sorted = []
    d = H.remove()
    while d:
        sorted.append(d)
        d = H.remove()
    return sorted
                
h = MaxHeap()
h.insert(50)


print(h.data)

h.remove()
print(h.data)
h.remove()
print(h.data)