힙
- 힙
힙의 특성(최소 힙 에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료 구조
우선순위 큐를 위하여 만들어진 자료구조
- heapq
Python 에서 힙의 구현체
최소 힙만 구현되어 있음
최소 힙의 특성 때문에 부모가 가장 작기 때문에 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현됨
기반 구현에서 우선순위 큐 ADT 는 주로 힙으로 구현하고 힙은 주로 배열로 구현되기 때문에 우선순위 큐는 배열로 구현함
- 특징
정렬된 구조가 아님
부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않음
- 이진 힙
자식이 둘인 힙
이진 트리가 널리 사용되는 이유와 비슷하게 이진 힙이 널리 사용됨
완전 이진 트리라서 배열에 순서대로 표현하기 적합함
배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용
- 힙 연산
- 뼈대
리스트로 초기화
0 번 인덱스를 사용하기 않기 위해 None 을 미리 설정
len 함수 None 을 위해 수정
- 삽입
힙에 요소를 삽입하는 연산
percolate_up 함수로 정의함
요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입한 뒤 부모 값과 비교해 값이 더 작은 경우 위치 변경 반복
- 추출
루트를 추출함
percolate_down 함수로 정의함
루트 추출 이후 비어 있는 루트에 가장 마지막 요소 올라가고 자식 노드와 값 비교해서 자식보다 크면 내려가는 다운힙 연산 수행
- 이진 힙 vs 이진 탐색 트리
힝븐 상/하 관계 보장하며 최소 힙에서는 부모가 항상 자식보다 작음
BST 는 좌/우 관계 보장하며 부모는 왼쪽 자식보다 크며 오른쪽 자식보다는 작거나 같음
탐색, 삽입을 하거나 모든 값이 정렬되어야 할 때는 BST(O(log n))
가장 큰/작은 값을 추출할때는 이진 힙 (O(1))