Heap 자료 구조 란?

Heap 자료 구조 란 무엇일까? 

 

아마 첨 들어 본 사람도 있을 거고 공부 했지만 시간이 지나면서 "어? heap이 머였지?" 라는 사람들도 있을거라고 생각합니다

 

왜냐하면 stack 이나 queue , tree 등은 한번 배우면 까먹기 쉽지 않은 자료 구조 지만 heap 같은 경우 tree 의 구조를 응용한 자료 구조 이므로 까먹거나 햇갈릴 수 도 있는 자료구조라고 생각합니다

 

heap 이란 우선순위 큐를 구현하기 위한 자료구조 로써 완전 이진 트리 로 이루어 저 있는 자료구조입니다

 

힙의 종류로는 최대 힙(max heap) 와 최소 힙(min heap)이 있습니다

 

힙은 배열로 구현 하는 것이 가장 효과적이다 !

 

먼저 최대 힙(max heap)은

부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리 입니다

value(부모) >= value(자식)

 

먼저 최소 힙(min heap)은

부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리 입니다

value(부모) <= value(자식)

 

힙의 구현

 

힙은 보통 배열로 저장하고 보통 인덱스 0은 사용하지 않는다! 

 

왼쪽 자식의 인덱스 = (부모 인덱스)*2;

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

부모의 인덱스 = (자식의 인덱스)/2;

 

힙의 삽입

 

새로운 노드가 들어오면 일단 마지막에 넣고 나서 힙의 성질을 만족시키도록 정렬시킨다!

 

힙의 삭제

 

최대 힙 인 경우 최댓값이 루트 노드 이므로 루트 노드가 삭제 된다 

그리고 나서 삭제된 루트 노드에서 힙의 마지막 노드를 가지고 온 다음에 재구성 한다!