해시(hash) & 힙(heap) 자료구조 개념 정리

해시(hash)

해시? 해시는 key-value 의 형태로 이루어져 있는 자료구조를 말한다.

 

파이썬에서의 해시 구현

파이썬에서의 해시 구현은 딕셔너리를 이용한다. 배열은 [] , 튜플은 () , 딕셔너리는 {}의 형태를 가지고 있으며 

다음과 같은 선언 방식을 가진다.

    value  = {
        'color' : 'green',
        'name' : 'smyoo'
    }

color라는 키값의 green이라는 value, name이라는 키값에 smyoo라는 value값을 가진다.

 

이하 파이썬에서 자주 사용하는 해시 사용법

- value[color] = red -> color라는 키 값에 red 라는 value 할당
- value.keys() -> 키를 전부 리스트 형태로 호출
- value.values() -> 값을 전부 리스트 형태로 호출
- value.has_key('name') -> name에 대한 키를 가지고 있는가?
- value.items() -> 딕셔너리에 저장된 데이터를 리스트 형태로 변환
- value.update(temp) -> temp라는 딕셔너리를 value라는 딕셔너리에 반영
- value.pop() -> 딕셔너리에서 해당 key 정보를 추출

 

힙(head) 

힙? 완전 이진 트리의 형태를 가지며, 우선 순위 큐를 구현하기 하며 '최대값 또는 최소값을 빠르게 찾기 위해' 고안된 자료구조

완전이진트리에 대한 설명 (*출처 - 동빈나 유투브 )

완전이진 트리란 자식노드가 '순서대로' 또는 '차례대로' 삽입되는 이진트리

우선순위큐에 대한 설명 (*출처 - 동빈나 유투브 )

힙을 이용한 우선순위 큐 구현이 시간 복잡도 측면에서 유리하다

힙 대한 설명 (*출처 - 동빈나 유투브 )

파이썬에서는 힙은 최소힙을 따른다. 또한 heapq 내장 모듈을 사용하여 구현한다. 

아래는 예제 코드

#노드 추가
import heapq
heap = []
heapq.heappush(heap, 1)

#노드 삭제
heapq.heappop(heap)

#리스트를 힙으로 바꾸기
heapq.heapify(list객체)


#최대힙 구하기
import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
       

( 주어진 메소드를 잘이용해서 최대, 최소를 빠르게 구현해보자. )