자료구조 - 힙(Heap)이란?

힙(Heap) 이란?

- 힙은 최댓값, 최솟값을 찾아내는 연산을 쉽게하기 위해 고안된 자료형이다.

- 힙(Heap)은 각 노드의 키(Key)값이 그 자식의 키값보다 작지않거나(최대 힙), 그 자식의 키값보다 크지 않은(최소 힙) 완전 이진 트리이다. 아래 그림은 최대힙(Max Heap)을 나타내는 그림이다.

 

 

최대 힙(Max Heap)

- 각 노드의 키값이 그 자식노드의 키값보다 큰 힙

최소 힙(Min Heap)

- 각 노드의 키값이 그 자식노드의 키값보다 작은 힙

 

힙 연산

아래의 연산들은 최대(Max Heap)힙을 기준으로 설명한다.

 

삽입 연산

- 힙은 완전이진트리의 구조를 유지해야 하므로 삽입시 트리의 가장 마지막에 원소를 추가하는 것으로 시작한다.

 

5를 키로 가지는 원소 삽입

1. 우선 힙은 완전이진트리의 구조를 유지해야 하므로 [3]노드의 왼쪽 자식노드로 새로운 노드가 삽입된다.

2. 그후 삽입된 형태의 힙이 힙의 조건을 만족하는지 확인한다.

 

3. 힙의 조건을 만족하므로 삽입 연산이 마무리된다.

 

6을 키로 가지는 원소 삽입

1. 마찬가지로 [3] 노드의 왼쪽자식 노드로 새로운 노드가 삽입된다.

   

2. 힙 조건을 검사한다, 6은 부모노드인 [3]의 키값5 보다 크므로 6과 5의 자리를 변경한다.

   

3. 다시 힙조건을 검사하고, 힙의 조건을 만족하므로 그대로 삽입 연산이 마무리된다.

 

10을 키로 가지는 원소 삽입

1. 마찬가지로 [3]노드의 왼쪽자식 노드로 새로운 노드가 삽입된다.

   

2. 힙 조건을 검사한다, 10은 부모노드인 [3]의 키값 5보다 크므로 10과 5의 자리를 변경한다.

   

3. 힙 조건을 다시 검사한다, 10은 루트 노드인[1]의 키값 9보다 크므로 9와 10의 자리를 다시 변경한다.

   

4. 루트노드에 위치하게 되었으므로 더 이상의 연산 없이 삽입 연산이 마무리된다.

 

삭제연산

- 힙은 최솟값, 최댓값을 쉽게 찾아내기위해 고안된 자료형이다. 따라서 삭제연산은 루트에서만 이루어진다.

- 루트에서 삭제가 이루어지면 당연히 다음에 루트가 될 노드가 정해져야 한다.

- 루트가 정해지면 다시 힙 조건에 만족하는지를 검사하며 이를 힙화(Heapify)해야한다.

1. 루트에서 노드가 삭제된다.
2. 완전 이진트리를 유지하기 위해 트리의 레벨 순서중 가장 마지막 노드를 루트로 옮긴다.
3. 루트로 옮겨진 노드와 두 자식노드중 더 큰 값을 가지는 노드와 비교하여 힙 조건을 검사한다.
4. 만족하지 않는다면 루트 노드와 자식 노드를 변경한다.
5. 다시 힙조건을 만족할 때까지 3,4번을 반복 진행한다.

 

 

파이썬 코드(백준-11279)

• 백준사이트에서 파이썬으로 알고리즘 작성시 입력을 input()으로 받게되면 상당한 시간이 걸린다. 따라서 sys를 import하여 sys.stdin.readline() 메소드를 이용해 입력을 받도록한다.

 

xxxxxxxxxx
import sys
class Heap:
    heap = []
    count = 0
    size = 0
​
    def __init__(self, size):
        self.heap = [-1 for i in range(0, size)]
        self.count = 0
        self.size = size
​
    #20씩 크기 증가
    def resizing(self):
        new_heap = [-1 for i in range(0, self.size + 20)]
        for i in range(0, self.size):
            new_heap[i] = self.heap[i]
        self.heap = new_heap
        self.size = self.size + 20
​
    def is_empty(self):
        if self.count is 0:
            return True
        return False
​
    def is_full(self):
        if self.count is self.size-1:
            return True
        return False
​
    def insert_node(self, key):
        if self.is_full():
            self.resizing()
​
        self.count += 1
        current_index = self.count
​
        while int(current_index/2) >= 1:
            if key <= self.heap[int(current_index/2)]:
                break
            self.heap[current_index] = self.heap[int(current_index/2)]
            current_index = int(current_index/2)
        self.heap[current_index] = key
​
    def delete_node(self):
        # 힙이 비었다면 0을 리턴
        if self.is_empty():
            return 0
​
        # 삭제될 원소의 값 기억
        delete_node = self.heap[1]
        # 마지막 원소를 루트로
        temp_node = self.heap[self.count]
        self.heap[1] = temp_node
        # 마지막 원소 삭제 처리
        self.heap[self.count] = -1
        # 노드 개수를 1 줄임
        self.count -= 1
​
        if self.count is 0:
            return delete_node
​
        current_node = 1
        child_node = current_node * 2 #왼쪽 자식 노드 (오른쪽 자식 노드 : 왼쪽 자식 노드 + 1)
        # 왼쪽노드가 전체 수보다 작으면 아직 비교대상이 존재한다는 것
        while child_node <= self.count:
            # 양쪽노드 존재(양쪽노드가 존재하지 않는다면 그냥 왼쪽 자식노드와 비교하면됨 따라서 else가 필요 없음)
            if child_node + 1 <= self.count:
                # 오른쪽 자식 노드가 더 크다면 그것을 비교 대상으로
                if self.heap[child_node] <= self.heap[child_node+1]:
                    child_node = child_node + 1
            # 루트에 놓인 마지막노드와 그 자식노드를 비교해가며 위치 조정
            if temp_node >= self.heap[child_node]:
                break
​
            self.heap[current_node] = self.heap[child_node]
            current_node = child_node
            child_node = child_node * 2
​
        self.heap[current_node] = temp_node
        return delete_node
​
​
if __name__ == "__main__":
    compute_count = int(sys.stdin.readline())
    heap = Heap(compute_count)
    for i in range(0, compute_count):
        compute = int(sys.stdin.readline())
        if compute is 0:
            print(heap.delete_node())
        else:
            heap.insert_node(compute)