[C & Java] Heap 힙

힙 (Heap)

완전 이진 트리 기반의 더미와 모습이 비슷한 자료구조

여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조

부모노드의 키 값이 자식 도느의 키 값보다 항상 큰 이진트리를 말한다.

부모노드와 자식 노드간에(루트 와 서브트리 간에) 위와 같은 조건이 항상 성립한다.

중복된 값을 허용한다. (이진 탐색트리는 안됨)

다른 용어로 이야기하면 히프안에서 데이터들은 느슨한 정렬 상태를 유지한다.

즉 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이다.

히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이므로(가장 큰 값은 루트 노드에 있음)

전체를 정렬할 필요는 없다.

히프는 완전 이진 트리이다.

힙의 종류

최대힙(Max Heap) : 부모노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리

최소 힙(Min Heap) : 부모노드의 키값이 자식 노드의 키값보다 작거나 같은 완전이진트리

힙의 구현

힙은 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있다.

이번호를 배열의 인덱스로 생각하면 배열에 핍의 노드들을 저장할 수있다.

구현을 쉽게 하기 위해 배열의 첫번째 인덱스 0은 사용하지 않고 1부터 시작한다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음을 유의

 

배열을 이용해 힙을 저장하면 완전 이진 트리에서처럼 자식 노드와 부모노드를 쉽게 알 수 있다.

노드 i의 왼쪽 자식 노드 인덱스 : i * 2

노드 i의 오른쪽 자식 노드 인덱스 : i * 2 + 1

부모의 인덱스 : 자식의 인덱스 / 2

 

Java로 힙 구현

삽입 연산

삭제 연산

힙의 복잡도 분석

힙정렬

힙정렬구현

힙의 복잡도

 

 

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기

 

참고

뇌를 자극하는 알고리즘(박상현 저)
C언어로 쉽게 풀어쓴 자료구조(개정 3판) - 생능 출판