[자료구조] 힙(heap)

우선순위 큐를 위하여 만들어진 자료구조

0 Intro

자료구조	삭제순서
스택	마지막에 들어온게 먼저 삭제된다.
큐	먼저 들어온 게 먼저 삭제된다.
우선순위큐	우선순위 가장 높은게 먼저 삭제된다.

• 우선순위 큐?
  데이터를이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
• 우선순위 큐 이용 사례
  시뮬레이션 시스템, 네트워크 트래픽제어, 운영체제작업스케쥴링
• 우선순위는 배열, 연결리스트, 힙으로 구현가능 하나 힙으로 하는게 효율적

1 정의

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

• 여러 개의 값들 중에서 최댓값이나 촤ㅣ솟값으 ㄹ빠르게 찾아내도록 만들어진 자료구조
• 일종의 반 정렬 상태(느슨한 정렬)
  • 부모노드가 우선순위 높은 것, 자식노드는 우선순위 낮은 것
• 힙 트리에서는 중복값을 허용 (이진탐색트리는 중복을 허용하지 않아요.)
• 최대힙, 최소힙

2 구현

힙을 저장하는 표준적인 자료구조는 배열이다.

• 보통 구현을 쉽게 하기 위해서 배여르이 첫 번째 인덱스인 0은 사용하지 않아요.
• 힙에서 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = 부모인덱스 *2
  • 오른쪽 자식 인덱스 = 부모인덱스 *2 +1
  • 부모 인덱스 = 자식인덱스 // 2

2-1 힙삽입

• 일단은 힙의 마지막 노드에 새로운 것을 삽입한다
• 새로운 노드와 그 부모 노드의 우선순위를 비교해서 힙으 ㅣ성질을 만족시킨다

ex) 최대힙에 새로운 요소 8을 삽입해보자

2-2 힙삭제

• 우선순위가 가장 높은건 루트노드이다. 즉 루트노드의 요소가 삭제된다.
• 삭제된 루트 노드에는 힙의 마지막 노드 요소를 가져온다.

ex) 최대 힙에서 최댓값을 삭제해보자.

3 코드

파이썬에서는 내장기능으로 heapq를 제공하고 있읍니다.

• 기본으로 최소힙만 제공

import heapq

heap = []

heapq.heappush(heap,2)
heapq.heappush(heap,1)
heapq.heappush(heap,5)
heapq.heappush(heap,7)
heapq.heappush(heap,4)
heapq.heappush(heap,9)
# [1,2,4,5,7,9] 의 힙구조

• 최대힙 제공

arr = [1,2,4,5,7,9]
heap=[]
for a in arr:
  heapq.heappush(heap,-a)
while heap:
  print(heapq.heappop(heap)*-1)