[자료구조] Heap

힙(Heap)

출처 : https://velog.io/@emplam27/

'완전' 이진트리를 기초로 하는 자료구조. 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리. 

• 최대값 혹은 최소값을 빠르게 찾기 위한 이진트리
• 우선 순위 큐를 위하여 만들어진 자료구조 (우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조)
• 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

출처 : https://gmlwjd9405.github.io/

시간복잡도

• 삽입 : logN
• 삭제 : logN

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)

최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)

 

 

힙(heap) 표현방식, 구현

힙을 저장하는 표준적인 자료구조는 배열이다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

 

힙에서의 부모 노드와 자식 노드의 관계

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2