Data Structure - Heap(2)

1. Heap 구현 - 데이터 삭제(pop)

- Heap은 최대값(max heap) 또는 최소값(min heap)만을 삭제한다. 그렇기에 root노드만을 삭제하면 된다. 

- root노드의 삭제는 root노드를 꺼내었을 때 발생하며, 이 동작을 pop이라고 명시한다. 

 

   def pop(self):
        # heap에 데이터가 없는 경우 
        if len(self.heap_array) <= 1:
            return None
            
        # heap에 데이터가 있는 경우 
        returned_data = self.heap_array[1]
        return returned_data 

 

 - 하지만, root노드를 제거하고 난 후에는 반드시 Heap의 데이터를 재정렬해야 한다. max heap의 경우, 가장 큰 값을 가진 노드가 새로운 root노드가 되고 min heap의 경우, 가장 작은 값을 가진 노드가 새로운 root노드가 된다. 

 

- 재정렬 과정은 아래 사진과 같다. 

 

- 위의 사진은 max heap으로, root노드 삭제 후 최대값을 찾기 위해 가장 마지막 index를 갖고 있는 노드를 사용한다. 

- * 데이터를 삽입할 때와 반대로, 재정렬을 하는 과정에서 좌측 자식노드가 없는 경우 재정렬을 멈춘다. 

- 좌측 자식노드가 존재하는 한, 데이터 비교를 통하여 재정렬을 수행한다. 

 

 

[재정렬 조건]

1) 좌측 자식노드가 없는 경우

→ 재정렬 종료 

 

2) 좌측 자식노드만 있는 경우

→ 1번 조건이 나올 때까지 비교 후 재정렬 필요

 

3) 좌/우측 자식노드가 모두 있는 경우

→ 먼저, 자식노드 간의 크기를 비교하여 둘 중 더 큰 노드와 비교 후 재정렬

→ 1번 조건이 나올 때까지 비교 후 재정렬 필요 

 

# root노드 삭제 후 데이터 재정렬 필요를 판단하기 위한 메소드 
def move_down(self,popped_index):
        left_child = popped_index * 2
        right_child = popped_index * 2 + 1
        
        # 재정렬 1번 조건- 좌측 자식노드가 없을 때
        if left_child >= len(self.heap_array): #배열의 길이보다 긴값 = 없는값 
            return False
        
        # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음)
        elif right_child >= len(self.heap_array):
            # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 
            if self.heap_array[popped_index] < self.heap_array[left_child]:
                return True #True - 재정렬이 필요하다. 
            else: 
                return False
        
        # 재정렬 3번 조건 - 좌우측 자식노드가 모두 존재 
        else:
            # 좌측 자식노드가 우측 자식노드보다 큰 경우 
            if self.heap_array[left_child] > self.heap_array[right_child]:
                # 좌측 자식노드가 새로운 root노드보다 크다면 
                if self.heap_array[popped_index] < self.heap_array[left_child]:
                    return True
                else:
                    return False
            # 우측 자식노드가 좌측 자식노드보다 큰 경우 
            else:
                if self.heap_array[popped_index] < self.heap_array[right_child]:
                    return True
                else:
                    return False
                    



 def pop(self):
        # heap에 데이터가 없는 경우 
        if len(self.heap_array) <= 1:
            return None
        # heap에 데이터가 있는 경우, 루트 노드를 변수에 저장 
        returned_data = self.heap_array[1]
        
        # 루트 노드 삭제 후 재정렬 준비
        # index -1은 가장 마지막 요소를 의미 
        self.heap_array[1] = self.heap_array[-1]
        
        # 마지막 노드가 루트노드로 올라갔으니 지워준다. 
        del self.heap_array[-1]
        
        # 재정렬 시작 
        popped_index = 1 
        while self.move_down(popped_index):# 재정렬이 필요하다면
            
            # 아래 코드는 move_down코드에서 약간의 변형이 추가된 코드 
            left_child = popped_index * 2
            right_child = popped_index * 2 + 1
        
            # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음)
            if right_child >= len(self.heap_array):
            # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 
                if self.heap_array[popped_index] < self.heap_array[left_child]:
                    # swap 
                    self.heap_array[popped_index], self.heap_array[left_child] = self.heap_array[left_child], self.heap_array[popped_index]
                    # 비교할 노드의 index 교체 
                    popped_index = left_child 
                    
            # 재정렬 3번 조건 - 좌우측 자식노드가 모두 존재 
            else:
                # 좌측 자식노드가 우측 자식노드보다 큰 경우 
                if self.heap_array[left_child] > self.heap_array[right_child]:
                    # 좌측 자식노드가 새로운 root노드보다 크다면 
                    if self.heap_array[popped_index] < self.heap_array[left_child]:
                        self.heap_array[popped_index], self.heap_array[left_child] = self.heap_array[left_child], self.heap_array[popped_index]
                        popped_index = left_child 
                # 우측 자식노드가 좌측 자식노드보다 큰 경우 
                else:
                    if self.heap_array[popped_index] < self.heap_array[right_child]:
                        self.heap_array[popped_index], self.heap_array[right_child] = self.heap_array[right_child], self.heap_array[popped_index]
                        popped_index = left_child
            
        return returned_data 

 

 

---

2. Heap 구현 - 전체 코드 

class Heap:
    def __init__(self, data):
        self.heap_array = list() # 배열(=리스트) 구조로 선언 
        self.heap_array.append(None) # 0번 인덱스를 비우는 작업 
        self.heap_array.append(data)
    
    
    # 2) 마지막에 삽입된 데이터의 index를 확인하여
    # 순서정렬 필요를 확인하는 메소드 
    def move_up(self, inserted_index):
        # 데이터가 없다면 삽입될 데이터가 root노드가 되기에 순서정렬 불필요
        if inserted_index <= 1: 
            return False
        else:
            parent_index = inserted_index // 2
            # 삽입된 값이 부모노드보다 큰 값인지 비교 
            if self.heap_array[inserted_index] > self.heap_array[parent_index]:
                return True
            else:
                return False 
    
    def insert(self, data):
        # 1) 데이터 추가
        # Heap 객체(배열)에 데이터가 없는 경우 
        if len(self.heap_array) == 0: 
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        
        # Heap 객체(배열)에 데이터가 있는 경우 
        self.heap_array.append(data)
        
        # 3) 데이터 순서 정렬 
        inserted_index = len(self.heap_array) - 1 # 가장 마지막에 삽입된 데이터 찾기 
        
        while self.move_up(inserted_index): # True = 순서정렬이 필요
            parent_index = inserted_index//2 # 부모노드의 index를 알아냄 
            # 위치를 바꿔줌. a:b = c:d의 구조로 서로 대응하는 값을 바꿔주는 알고리즘 
            self.heap_array[inserted_index], self.heap_array[parent_index] = self.heap_array[parent_index], self.heap_array[inserted_index]
            inserted_index = parent_index #index 또한 바꿔준다. 
        
        return True 
            
    
    def pop(self):
        # heap에 데이터가 없는 경우 
        if len(self.heap_array) <= 1:
            return None
        # heap에 데이터가 있는 경우, 루트 노드를 변수에 저장 
        returned_data = self.heap_array[1]
        
        # 루트 노드 삭제 후 재정렬 준비
        # index -1은 가장 마지막 요소를 의미 
        self.heap_array[1] = self.heap_array[-1]
        
        # 마지막 노드가 루트노드로 올라갔으니 지워준다. 
        del self.heap_array[-1]
        
        # 재정렬 시작 
        popped_index = 1 
        while self.move_down(popped_index):# 재정렬이 필요하다면
            
            # 아래 코드는 move_down코드에서 약간의 변형이 추가된 코드 
            left_child = popped_index * 2
            right_child = popped_index * 2 + 1
        
            # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음)
            if right_child >= len(self.heap_array):
            # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 
                if self.heap_array[popped_index] < self.heap_array[left_child]:
                    # swap 
                    self.heap_array[popped_index], self.heap_array[left_child] = self.heap_array[left_child], self.heap_array[popped_index]
                    # 비교할 노드의 index 교체 
                    popped_index = left_child 
                    
            # 재정렬 3번 조건 - 좌우측 자식노드가 모두 존재 
            else:
                # 좌측 자식노드가 우측 자식노드보다 큰 경우 
                if self.heap_array[left_child] > self.heap_array[right_child]:
                    # 좌측 자식노드가 새로운 root노드보다 크다면 
                    if self.heap_array[popped_index] < self.heap_array[left_child]:
                        self.heap_array[popped_index], self.heap_array[left_child] = self.heap_array[left_child], self.heap_array[popped_index]
                        popped_index = left_child 
                # 우측 자식노드가 좌측 자식노드보다 큰 경우 
                else:
                    if self.heap_array[popped_index] < self.heap_array[right_child]:
                        self.heap_array[popped_index], self.heap_array[right_child] = self.heap_array[right_child], self.heap_array[popped_index]
                        popped_index = left_child
            
        return returned_data 
    
        
    # root노드 삭제 후 데이터 재정렬 필요를 판단하기 위한 메소드 
    def move_down(self,popped_index):
        left_child = popped_index * 2
        right_child = popped_index * 2 + 1
        
        # 재정렬 1번 조건- 좌측 자식노드가 없을 때
        if left_child >= len(self.heap_array): #배열의 길이보다 긴값 = 없는값 
            return False
        
        # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음)
        elif right_child >= len(self.heap_array):
            # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 
            if self.heap_array[popped_index] < self.heap_array[left_child]:
                return True #True - 재정렬이 필요하다. 
            else: 
                return False
        
        # 재정렬 3번 조건 - 좌우측 자식노드가 모두 존재 
        else:
            # 좌측 자식노드가 우측 자식노드보다 큰 경우 
            if self.heap_array[left_child] > self.heap_array[right_child]:
                # 좌측 자식노드가 새로운 root노드보다 크다면 
                if self.heap_array[popped_index] < self.heap_array[left_child]:
                    return True
                else:
                    return False
            # 우측 자식노드가 좌측 자식노드보다 큰 경우 
            else:
                if self.heap_array[popped_index] < self.heap_array[right_child]:
                    return True
                else:
                    return False
        
        

 

 

 

[기능 테스트] 

---

3. Heap - 시간복잡도 

- Heap의 depth(깊이/레벨)를 h라고 표기한다면, n개의 노드를 가지는 heap에 데이터를 삽입 또는 삭제할 때 최악의 경우 root노드에서 부터 leaf(terminal)노드까지 비교작업을 수행해야 하므로 h = log n에 가깝다. 그러므로 시간복잡도는 O(log n)이다.

 

- 다시 말해, 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

 

* 참고: 빅오 표기법에서 log n 에서의 log의 밑은 10이 아니라, 2이다.