힙

힙

힙이란 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.
힙은 오로지 부모노드와 자식노드 간에만 대소관계가 성립하고 형제노드 사이에서는 대소관계가 정해지지 않는다.
추가적으로 이진 탐색 트리는 형제노드간 대소관계가 정해진다. 즉 부모노드를 기준으로 왼쪽 자식은 최소값, 오른쪽 자식은 최대값이 들어간다.

힙 자료구조에 insert하는 함수 구현

1. 맨 끝의 위치에 노드를 생성한다.

self.data.append(x)

파이썬에서는 append를 하게 되면 맨 끝에 노드를 생성할 수 있다.

2. 만약 배열의 길이가 1이면 자식노드를 탐색할 수가 없으므로 조건을 추가한다.

if len(self.data) == 1:
            return

3. 새 노드를 부모 노드와 비교하여 부모 노드보다 작을 경우 부모 노드와 위치 변경한다.

		idx_c = len(self.data) - 1
        while True:
            idx_p = int((idx_c - 1)/2)

            if idx_c == 0:
                break

            if self.data[idx_c] < self.data[idx_p]:
                self.swap(idx_c, idx_p)
                idx_c = idx_p
            else:
                break

idx_c는 현재 삽입한 노드인덱스다. (마지막 위치에 노드를 생성한 것이므로 결국 배열의 길이 - 1)
idx_p는 부모 노드 인덱스이다.
만약 부모노드값보다 자식노드값이 작다면 스왑한다. 그리고 현재 삽입한 노드 idx_c를 부모 노드 인덱스 idx_p로 바꾼다.
그렇지 않으면 바꿀 필요가 없으므로 종료한다.

4. 스왑함수 구현

def swap(self, idx_c, idx_p):     
        tmp = self.data[idx_c]
        self.data[idx_c] = self.data[idx_p]
        self.data[idx_p] = tmp

힙 자료구조에 delete하는 함수 구현

1. root 노드를 삭제한다. 0번째 인덱스를 삭제한다는 의미이다. 그리고 맨 끝에 있는 노드를 root로 올린다.

self.data[0] = self.data.pop()
idx_c = 0

현재 인덱스 idx_c를 0으로 둔다.

2. 맨 끝에 있는 노드를 root로 옮겼다. 그 노드의 자식노드를 비교하여 자식노드보다 클 경우 위치 변경한다. (자식 노드는 2개이다. 자식 노드 중에서 더 작은 값을 스왑한다.)

		while True:        
            idx_child_1 = (idx_c + 1) * 2 - 1
            idx_child_2 = (idx_c + 1) * 2

            if idx_child_1 >= len(self.data): # 자식 노드가 없는 경우
                break
            elif idx_child_2 == len(self.data): # 자식 노드가 왼쪽만 있을 경우
                idx_child = idx_child_1
            else: ## 자식 노드가 둘 다 있는 경우
                
                if self.data[idx_child_1] <= self.data[idx_child_2]:
                    idx_child = idx_child_1
                else:
                    idx_child = idx_child_2
                    
            if self.data[idx_child] < self.data[idx_c]:
                self.swap(idx_child, idx_c)
                idx_c = idx_child
            else:
                break

idx_child_1은 자식 노드 중 left 위치한 자식 노드이다.
idx_child_2는 자식 노드 중 right 위치한 자식 노드이다.
반복문을 탈출한 조건을 만들어야 한다.
즉 idx_child_1이 배열의 길이보다 크거나 같다면 자식 노드가 없다는 의미이므로 종료한다.
반면에 idx_child_2가 배열의 길이와 같다면 자식 노드는 왼쪽만 있을 경우이다.
자식 노드가 둘 다 있을 때에는 idx_child_1값과 idx_child_2값을 비교해 더 작은 값을 idx_child에 저장한다.
그리고 현재 idx_c와 idx_child과 비교한다. 만약 더 크다면 위치를 바꾼다.

전체코드

class heap:
    def __init__(self):
        self.data = []
    def swap(self, idx_c, idx_p):     
        tmp = self.data[idx_c]
        self.data[idx_c] = self.data[idx_p]
        self.data[idx_p] = tmp
    ## 삽입방법
    ## 1. 맨 끝의 위치에 노드를 생성
    ## 2. 새 노드를 부모 노드와 비교하여 부모 노드보다 작을 경우
    ## 부모 노드와 위치 변경
    ## 3. 더 이상 위치가 바뀌지 않을 때까지 반복
        
    def insert(self, x):
        self.data.append(x)

        if len(self.data) == 1:
            return
        
        idx_c = len(self.data) - 1
        while True:
            idx_p = int((idx_c - 1)/2)

            if idx_c == 0:
                break

            if self.data[idx_c] < self.data[idx_p]:
                self.swap(idx_c, idx_p)
                idx_c = idx_p
            else:
                break
    ## 1. root 노드 삭제
    ## 2. 맨 끝에 있는 노드를 root로 올림
    ## 3. 노드 a를 자식 노드와 비교하여 자식 노드보다 클 경우 위치 변경
        ## 자식 노드 2개 중에서 더 작은 값 스왑
    ## 4. 더 이상 위치가 바뀌지 않을 때 까지 반복
    def delete(self):
        self.data[0] = self.data.pop()
        idx_c = 0

        while True:        
            idx_child_1 = (idx_c + 1) * 2 - 1
            idx_child_2 = (idx_c + 1) * 2

            if idx_child_1 >= len(self.data): # 자식 노드가 없는 경우
                break
            elif idx_child_2 >= len(self.data): # 자식 노드가 왼쪽만 있을 경우
                idx_child = idx_child_1
            else: ## 자식 노드가 둘 다 있는 경우
                
                if self.data[idx_child_1] <= self.data[idx_child_2]:
                    idx_child = idx_child_1
                else:
                    idx_child = idx_child_2
                    
            if self.data[idx_child] < self.data[idx_c]:
                self.swap(idx_child, idx_c)
                idx_c = idx_child
            else:
                break
 

h = heap()
h.data
h.insert(1)
h.insert(2)
h.insert(3)
h.insert(3)
h.insert(4)
h.insert(7)
h.insert(9)
h.insert(5)
h.insert(4)
h.insert(8)