[자료구조/python] 복습 4. Heap

Heap

• 완전 이진 트리 형태의 우선순위 큐를 위하여 만들어진 자료구조
• 최소값(최소 힙) 또는 최대값(최대 힙)을 빠르게 찾아내는데 유용한 자료구조
• 중복 값을 허용(이진 탐색 트리에서는 중복값을 허용하지 않음)
• 반 정렬 상태(큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다는 정도)

최소힙

key(부모 노드) ≥ key(자식 노드) 의 형태를 가지는 힙

 

최대힙

key(부모 노드) ≤ key(자식 노드) 의 형태를 가지는 힙

 

Heap의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다
• 구현을 쉽게 하기 위하여 인덱스 0은 사용되지 않는다
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다
• 힙에서의 부모 노드와 자식 노드의 관계
  • 부모 인덱스 = (자식 인덱스) // 2
  • 왼쪽 자식 인덱스 = (부모 인덱스) * 2
  • 오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1

Heap의 삽입 (시간 복잡도 : O(logn))

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다
2. 해당 힙의 규칙(부모 노드 이하이거나 이상이거나)을 만족할 때까지 새로운 노드를 부모 노드와 교환한다

Heap의 삭제 (시간 복잡도 : O(logn))

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제 된다
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다
3. 힙을 재구성한다

 

구현

참고 블로그

 

Heap 삽입

# 힙 노드 삽입
    def insert(self, n):
        self.queue.append(n)
        last_index = len(self.queue) - 1
        while 0 <= last_index:
            parent_index = self.parent(last_index)
            if 0 <= parent_index and self.queue[parent_index] < self.queue[last_index]:
                self.swap(last_index, parent_index)
                last_index = parent_index
            else:
                break
            
    def swap(self, i, parent_index):
        self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
    
    def parent(self, index):
        return (index - 1) // 2

 

Heap 삭제

# 힙 노드 삭제
    def delete(self):
        last_index = len(self.queue) - 1
        if last_index < 0 :
            return -1
        
        self.swap(0, last_index) # 루트노드와 끝노드 교환
        max_value = self.queue.pop() # 끝노드(이전의 루트 노드 삭제)
        self.maxHeapify(0) # root에서부터 재정렬 
        print(max_value)
        return max_value
    
    def maxHeapify(self, i):
        left_index = self.leftChild(i)
        right_index = self.rightChild(i)
        max_index = i
        
        # max_index 보다 자식노드가 있는지 확인
        if left_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[left_index]:
            max_index = left_index
        if right_index <= len(self.queue) -1 and self.queue[max_index] < self.queue[right_index]:
            max_index = right_index
        
        if max_index != i :
            self.swap(i, max_index)
            self.maxHeapify(max_index)
            
    def leftChild(self, index):
        return index * 2 + 1
    
    def rightChild(self, index):
        return index * 2 + 2

 

전체

class MaxHeap(object):
    def __init__(self):
        self.queue = []
    
    # 힙 노드 삽입
    def insert(self, n):
        self.queue.append(n)
        last_index = len(self.queue) - 1
        while 0 <= last_index:
            parent_index = self.parent(last_index)
            if 0 <= parent_index and self.queue[parent_index] < self.queue[last_index]:
                self.swap(last_index, parent_index)
                last_index = parent_index
            else:
                break
            
    def swap(self, i, parent_index):
        self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
    
    def parent(self, index):
        return (index - 1) // 2
    
    # 힙 노드 삭제
    def delete(self):
        last_index = len(self.queue) - 1
        if last_index < 0 :
            return -1
        
        self.swap(0, last_index) # 루트노드와 끝노드 교환
        max_value = self.queue.pop() # 끝노드(이전의 루트 노드 삭제)
        self.maxHeapify(0) # root에서부터 재정렬 
        print(max_value)
        return max_value
    
    def maxHeapify(self, i):
        left_index = self.leftChild(i)
        right_index = self.rightChild(i)
        max_index = i
        
        # max_index 보다 자식노드가 있는지 확인
        if left_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[left_index]:
            max_index = left_index
        if right_index <= len(self.queue) -1 and self.queue[max_index] < self.queue[right_index]:
            max_index = right_index
        
        if max_index != i :
            self.swap(i, max_index)
            self.maxHeapify(max_index)
            
    def leftChild(self, index):
        return index * 2 + 1
    
    def rightChild(self, index):
        return index * 2 + 2