Home 힙(Heap)구조에서 삽입과 삭제!
Post
Cancel

힙(Heap)구조에서 삽입과 삭제!

Posted Sep 19, 2022 Updated Sep 19, 2022
By 김경민
10 min read

힙(heap)

힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 왼쪽부터 차례로 채운다 생각해면 됨

힙을 사용하는 이유

  • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
  • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으려면, O(log n)이 걸림
  • 우선 순위 큐와 같이 최대값 또는 최소값을 바르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

힙의 구조

  • 최대 힙, 최소 힙으로 분류할 수 있다.
  • 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.(최대힙경우)
  • 완전 이진 트리 형태를 가진다
  • 완전 이진 트리이기 때문에 수학적 패턴으로 배열을 활용할 수 있다

힙의 동작

하단에서 다시 한번 언급하며 구현할 것.
  • 데이터의 삽입
    • 최하단(배열의 마지막)에 노드를 넣고 부모 노드보다 크면 자리를 바꿔주는 형식이다.
    • 고로 루트 노드가 가장 큰 값이 되고, 자식 노드의 크기는 순서 없이 저장된다.
    • 번외) 트리는 왼쪽 끝 자식 노드의 값이 가장 작고, 오른쪽 끝 자식 노드가 가장 크다.
  • 데이터의 삭제
    • 보통 루트 노드를 삭제하는 것이 일반적(가장 큰 값을 삭제)
    • 상단을 제거하고 가장 하단부 왼쪽에 위치한 노드(배열의 마지막)를 루트 노드로 이동
    • 루트 노드의 값이 자식 노드의 값 중 보다 큰 것이 있는지 확인
    • 큰 것이 있다면 두개의 자식 노드 중 더 큰 것과 바꿔주는 것을 반복한다.

힙과 배열

  • 일반적으로 힙 구현시 배열 자료구조를 활용함
  • 배열은 인덱스가 0번부터 시작하지만, 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 수월함
    • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
    • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
    • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

예) 10노드(인덱스=2)의 부모인덱스와 자식인덱스

부모 : 2//2=1, 왼쪽 자식 : 2*2 = 4, 오른쪽 자식 : 2*2+1 = 5

데이터 삽입하기

  • 최하단(배열의 마지막)에 노드를 넣고 부모 노드보다 크면 자리를 바꿔주는 형식이다.
  • 고로 루트 노드가 가장 큰 값이 되고, 자식 노드의 크기는 순서 없이 저장된다.
  • 번외) 트리는 왼쪽 끝 자식 노드의 값이 가장 작고, 오른쪽 끝 자식 노드가 가장 크다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 0번인덱스를 지정함으로써 root인덱스는 1번이 됨
        self.heap_array.append(data) # root노드에 data삽입
        
    def move_up(self,insert_idx):
        if insert_idx == 1:
            return False
        
        parent_idx = insert_idx//2
        if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
            return True
        
        return False
        
        
    def insert(self, data):
        # 1 최하단(배열의 마지막)에 노드를 넣었음
        self.heap_array.append(data)

        insert_idx = len(self.heap_array) - 1 # 부모 노드를 파악하기 위해 현재 인덱스를 구함(-1은 None이 있기 때문)
        # 부모 노드보다 큰지에 대한 여부를 함수를 통해 판단하고 반복함
        while self.move_up(insert_idx):
            self.heap_array[insert_idx],self.heap_array[insert_idx//2] = self.heap_array[insert_idx//2],self.heap_array[insert_idx]
            insert_idx = insert_idx//2

1
2
3
4
5
6
7
8
9
10

heap = Heap(15)
heap.heap_array
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
print(heap.heap_array)
heap.insert(20)
print(heap.heap_array)


1
2

[None, 15, 10, 8, 5, 4]
[None, 20, 10, 15, 5, 4, 8]

데이터의 삭제

  • 보통 루트 노드를 삭제하는 것이 일반적(가장 큰 값을 삭제)
  • 상단을 제거하고 가장 하단부 왼쪽에 위치한 노드(배열의 마지막)를 루트 노드로 이동
  • 루트 노드의 값이 자식 노드의 값 중 보다 큰 것이 있는지 확인
  • 큰 것이 있다면 두개의 자식 노드 중 더 큰 것과 바꿔주는 것을 반복한다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Heap:
    def __init__(self,data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_down(self, popped_idx):
        
        # case 1. 부모의 자식 노드가 2개 있을 때
            # 설명을 붙이자면 popped_idx는 현재 부모 노드이다.
            # 배열의 길이가 왼쪽 자식 노드의 위치 보다 크다면?
            # 자식 노드는 2개이다
            # -1의 이유는 None이 처음에 포함됐기 때문이다.
        if len(self.heap_array)-1 > popped_idx*2:
            # 두개의 자식 노드 중 하나라도 부모보다 클 때 True를 반환하여 바꿔줄 수 있다.
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2] or self.heap_array[popped_idx] < self.heap_array[popped_idx*2 +1]:
                return True
        #case 2. 부모의 자식 노드가 1개 있을 때
        elif len(self.heap_array)-1 == popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2]:
                return True
        #case 3. 부모의 자식노드가 없을 때
            # 위에서 2개일 때와 1개일 때를 제외하면 없는 경우이다.
        return False
    
    def pop(self):
        # 루트 노드 삭제하기
        if len(self.heap_array) <= 1:
            return None
        # 빼줄 데이터(확인용)
        returned_data = self.heap_array[1]
        # 가장 마지막 데이터(배열의 마지막 데이터)와 루트 데이터를 바꿔준다.
        self.heap_array[1] = self.heap_array[-1]
        # 마지막 데이터를 삭제
        del(self.heap_array[-1])
        
        #루트 데이터를 뺐기때문에 루트 데이터의 인덱스는 1이다
        popped_idx = 1
        while self.move_down(popped_idx):
            # 자식 노드가 1개만 있을 경우(왼쪽만 있게 됨) 오른쪽 자식노드의 인덱스 값을 사용하면 에러가 나기에 try except구문 활용
            try:
                # 왼쪽 자식 노드가 클 경우
                if self.heap_array[popped_idx*2] > self.heap_array[popped_idx*2+1]:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2
                # 오른쪽 자식 노드가 클 경우
                else:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2+1]=self.heap_array[popped_idx*2+1],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2 + 1
            # 자식 노드가 하나 일 경우(왼쪽 자식만 있음)
            except IndexError:
                self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                popped_idx = popped_idx*2                
        return returned_data

1
2
3

print(heap.heap_array)
heap.pop()
print(heap.heap_array)

1
2

[None, 20, 10, 15, 5, 4, 8]
[None, 15, 10, 8, 5, 4]

합친 코드(주석x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_up(self,insert_idx):
        if insert_idx == 1:
            return False
        
        parent_idx = insert_idx//2
        if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
            return True
        
        return False
        
    def insert(self, data):
        self.heap_array.append(data)
        insert_idx = len(self.heap_array) - 1
        
        while self.move_up(insert_idx):
            self.heap_array[insert_idx],self.heap_array[insert_idx//2] = self.heap_array[insert_idx//2],self.heap_array[insert_idx]
            insert_idx = insert_idx//2
            
    def move_down(self, popped_idx):
        if len(self.heap_array)-1 > popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2] or self.heap_array[popped_idx] < self.heap_array[popped_idx*2 +1]:
                return True
        elif len(self.heap_array)-1 == popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2]:
                return True

        return False
    
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del(self.heap_array[-1])
        
        popped_idx = 1
        while self.move_down(popped_idx):
            try:
                if self.heap_array[popped_idx*2] > self.heap_array[popped_idx*2+1]:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2
                else:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2+1]=self.heap_array[popped_idx*2+1],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2 + 1

            except IndexError:
                self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                popped_idx = popped_idx*2
                
        return returned_data

이미지 출처 : 잔재미코딩

algorithm heap
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents