[TIL] 힙 - Heap

힙(Heap)이란?  

• 완전 이진 트리(Complete Binary Tree) - 최대/최소값을 빠르게 찾기 위함
• max heap과 min heap으로 분류 (최대값/최소값을 구하기 위한 구조)
• 각 노드의 값 >= 해당노드의 자식노드 값 (max heap) (min heap은 반대)
• 힙 구현시 배열 자료구조를 사용

* 완전 이진 트리 : 노드 삽입 시 가장 하단의 왼쪽 노드부터 차례대로 삽입하는 트리

힙 vs 이진 탐색 트리?
  -힙 : 최대/최소값 검색을 위한 구조
  -이진 탐색 트리 : 탐색을 위한 구조

 

힙의 인덱스 구조

• 부모 노드의 인덱스 번호 = 자식 노드 인덱스 번호 // 2
• 왼쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2+1

 

힙 구현 (max heap)

1. 힙 클래스 구현

class Heap:
	def __init__(self, data):
    	self.heap_arr = list()		#일반적으로 배열로 구현
        self.heap_arr.append(None)	#루트 노드의 인덱스 번호를 1로 하기 위해 None 삽입
        self.heap_arr.append(data)

 

2. 힙 데이터 삽입(insert)

    - 데이터 삽입 시 해당 데이터의 값을 부모 노드와 비교하여 큰 경우 위로 올려주는 swap 처리를 해야한다.

    - swap_up 함수를 따로 만들어 해당 노드를 swap 처리해야하는지 판별하도록 한다.

 

def swap_up(self, ins_idx):
	if ins_idx <=1:		# 삽입한 데이터가 루트 노드인 경우 swap처리 불필요
    	return False
	
    parent_idx = ins_idx //2
    if self.heap_arr[ins_idx] > self.heap_arr[parent_idx]:
        return True
    else:
        return False

def insert(self, data):
    if len(self.heap_arr) == 0:		# 힙에 아무것도 없을 경우 초기화 과정
        self.heap_arr.append(None)
        self.heap_arr.append(data)
        return True

    self.heap_arr.append(data)
    ins_idx = len(self.heap_arr)-1	# 루트 노드 인덱스를 1로 설정하였으므로
    
    while self.swap_up(ins_idx):
        parent_idx = ins_idx//2
        self.heap_arr[ins_idx], self.heap_arr[parent_idx] = self.heap_arr[parent_idx], self.heap_arr[ins_idx]
        ins_idx = parent_idx

    return True

 

2. 힙 데이터 삭제 (pop)

    - 데이터 삭제 시 일반적으로 루트노드를 삭제한다. (최대값 or 최소값)

    - 삭제 후 가장 마지막에 추가한 노드를 root 노드로 이동한 후 자식 노드와 값을 비교하여 swap 처리한다.

    - swap_down 함수를 따로 만들어 해당 노드를 swap 처리해야하는지 판별하도록 한다.

def swap_down(self, pop_idx):
    left_idx = pop_idx*2
    right_idx = pop_idx*2+1
    
    # 노드가 존재하지 않을 때 swap 처리 불필요
    if left_idx >= len(self.heap_arr):
        return False

    # 왼쪽 자식 노드만 존재할 때
    elif right_idx >= len(self.heap_arr):
        if self.heap_arr[pop_idx] < self.heap_arr[left_idx]:
            return True
        else:
            return False

    # 왼쪽, 오른쪽 모든 노드가 존재할 때
    else:
        if self.heap_arr[left_idx] >  self.heap_arr[right_idx]
            if self.heap_arr[left_idx] > self.heap_arr[pop_idx]:
                return True
            else:
                return False
        else:
            if self.heap_arr[right_idx] > self.heap_arr[pop_idx]:
                return True
            else:
                return False

def pop(self):
    if len(self.heap_arr) <=1:		#힙에 None만 존재하거나 데이터가 존재하지 않을 경우 
        return None

    return_data = self.heap_arr[1]
    self.heap_arr[1] = self.heap_arr[-1]		#가장 마지막에 추가한 노드와 교환 후 삭제
    del self.heap_arr[-1]
    pop_idx = 1							#swap_down을 하기 위한 인덱스 설정

    while self.swap_down(pop_idx):
        left_idx = pop_idx*2
        right_idx = pop_idx*2+1

        # 왼쪽 자식 노드만 있을 경우
        if right_idx >= len(self.heap_arr):
            if self.heap_arr[pop_idx] < self.heap_arr[left_idx]:
                self.heap_arr[pop_idx],self.heap_arr[left_idx] = self.heap_arr[left_idx], self.heap_arr[pop_idx]
                pop_idx = left_idx				#인덱스 재설정   
        #모든 노드가 존재할 경우
        else:
            if self.heap_arr[left_idx] > self.heap_arr[right_idx]:
                if self.heap_arr[pop_idx] < self.heap_arr[left_idx]:
                    self.heap_arr[pop_idx],self.heap_arr[left_idx] = self.heap_arr[left_idx], self.heap_arr[pop_idx]
                    pop_idx = left_idx
            else:
                if self.heap_arr[pop_idx] < self.heap_arr[right_idx]:
                    self.heap_arr[pop_idx],self.heap_arr[right_idx] = self.heap_arr[right_idx], self.heap_arr[pop_idx]
                    pop_idx = right_idx

    return return_data			#삭제한 데이터 반환

 

 

힙의 시간복잡도는?
트리의 높이(Depth)를 h라 한다면, 최악의 경우 root에서 leaf 까지 비교하여 h = logn에 가깝다.
따라서 시간복잡도는 O(logn)

* 실행 시 50% 즉, 절반의 실행시간을 단축시킬 수 있으므로

 

 

*본 내용은 패스트 캠퍼스 강의를 참고하였습니다.